linguistic:voice_change
Definition

The shortest path problem can be defined for graphs whether undirected, directed, or mixed. Here it is defined for undirected graphs; for directed graphs the definition of path requires that consecutive vertices be connected by an appropriate directed edge.

Two vertices are adjacent when they are both incident to a common edge.A path in an undirected graph is a sequence of vertices P = (v 1, v 2, …, v n) ∈ V × V × ⋯ × V {\displaystyle P=(v_{1},v_{2},\ldots,v_{n})\in V\times V\times \cdots \times V} such that v i {\displaystyle v_{i}} is adjacent to v i + 1 {\displaystyle v_{i+1}} for 1 ≤ i < n {\displaystyle 1\leq i<n}.Such a path P {\displaystyle P} is called a path of length n − 1 {\displaystyle n-1} from v 1 {\displaystyle v_{1}} to v n {\displaystyle v_{n}}.(The v i {\displaystyle v_{i}} are variables; their numbering here relates to their position in the sequence and needs not to relate to any canonical labeling of the vertices.)

Let E = { e i, j } {\displaystyle E=\{e_{i,j}\}} where e i, j {\displaystyle e_{i,j}} is the edge incident to both v i {\displaystyle v_{i}} and v j {\displaystyle v_{j}}. Given a real-valued weight function f: E → R {\displaystyle f:E\rightarrow \mathbb {R} }, and an undirected (simple) graph G {\displaystyle G}, the shortest path from v {\displaystyle v} to v ′ {\displaystyle v'} is the path P = (v 1, v 2, …, v n) {\displaystyle P=(v_{1},v_{2},\ldots,v_{n})} (where v 1 = v {\displaystyle v_{1}=v} and v n = v ′ {\displaystyle v_{n}=v'}) that over all possible n {\displaystyle n} minimizes the sum ∑ i = 1 n − 1 f (e i, i + 1). {\displaystyle \sum _{i=1}^{n-1}f(e_{i,i+1}).} When each edge in the graph has unit weight or f: E → { 1 } {\displaystyle f:E\rightarrow \{1\}}, this is equivalent to finding the path with fewest edges.

The problem is also sometimes called the single-pair shortest path problem, to distinguish it from the following variations:

These generalizations have significantly more efficient algorithms than the simplistic approach of running a single-pair shortest path algorithm on all relevant pairs of vertices.