Basics of shortest paths
Path lengths and distances
Let [math]\displaystyle{ G=(V,A) }[/math] be a simple directed graph and for each arc [math]\displaystyle{ a\in A }[/math] let [math]\displaystyle{ \ell(a) }[/math] be a real number, the length of [math]\displaystyle{ a }[/math].
- The length of an ordinary path (incl. ordinary cycles) is the sum of the lengths of all arcs on this path.
- Depending on the context, the length of a generalized path (incl. generalized cycles) is either defined identically to ordinary paths or, alternatively, the lengths of the backward arcs are not added but subtracted.
- If the length of an ordinary or generalized cycle is negative, this cycle is called a negative cycle.
- For two nodes, [math]\displaystyle{ s,t\in V }[/math]:
- A shortest path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] is an [math]\displaystyle{ (s,t) }[/math]-path with minimum length among all [math]\displaystyle{ (s,t) }[/math]-paths.
- The distance from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] is the length of a shortest [math]\displaystyle{ (s,t) }[/math]-path. If no [math]\displaystyle{ (s,t) }[/math]-path exists, the distance is [math]\displaystyle{ +\infty }[/math] (the neutral value of the arithmetic operation, "taking the minimum of two values").
Remarks:
- In this context, undirected graphs are usually regarded as symmetric directed graphs such that two mutually opposite arcs have the same length.
- If there are no negative cycles, the distances from a node to itself is zero because the trivial path with no arcs has length zero.
Subpath property of shortest paths
Statement: For [math]\displaystyle{ s,t\in V }[/math] let [math]\displaystyle{ p }[/math] be a shortest [math]\displaystyle{ (s,t) }[/math]-path. Let [math]\displaystyle{ v,w\in V }[/math] be two nodes on [math]\displaystyle{ p }[/math] such that [math]\displaystyle{ v }[/math] precedes [math]\displaystyle{ w }[/math] on [math]\displaystyle{ p }[/math]. Then the subpath of [math]\displaystyle{ p }[/math] from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math] is a shortest [math]\displaystyle{ (v,w) }[/math]-path.
Proof: Let [math]\displaystyle{ p_1 }[/math], [math]\displaystyle{ p_2 }[/math] and [math]\displaystyle{ p_3 }[/math] denote the subpaths of [math]\displaystyle{ p }[/math] from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math], from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math], and from [math]\displaystyle{ w }[/math] to [math]\displaystyle{ t }[/math], respectively. Suppose for a contradiction that some [math]\displaystyle{ (v,w) }[/math]-path [math]\displaystyle{ p'_2 }[/math] is shorter than [math]\displaystyle{ p_2 }[/math]. Then the concatenation [math]\displaystyle{ p_1+p'_2+p_3 }[/math] would be a shorter [math]\displaystyle{ (s,t) }[/math]-path than [math]\displaystyle{ p }[/math].
Remark: Usually, only the case [math]\displaystyle{ v=s }[/math] is considered. That restricted version is called the prefix property.
Valid distance property
Definition: For each node [math]\displaystyle{ u\in V }[/math] let [math]\displaystyle{ d(u) }[/math] be some real number. We say that [math]\displaystyle{ d }[/math] fulfills the valid distance property if [math]\displaystyle{ d(w)\leq d(v)+\ell(v,w) }[/math] for all arcs [math]\displaystyle{ (v,w)\in A }[/math].
Statement: Let [math]\displaystyle{ s\in V }[/math] and for each node [math]\displaystyle{ u\in V }[/math] let [math]\displaystyle{ d(u) }[/math] be the distance from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ u }[/math] with respect to the arc lengths [math]\displaystyle{ \ell }[/math]. For all [math]\displaystyle{ (v,w)\in A }[/math], it is [math]\displaystyle{ d_\ell(w)\leq d_\ell(v)+\ell(v,w) }[/math], that is, the valid distance property is fulfilled.
Proof: The left-hand side of the inequality is the length of a shortest [math]\displaystyle{ (s,w) }[/math]-path, whereas the right-hand side is the length of some [math]\displaystyle{ (s,w) }[/math]-path (viz. the concatenation of a shortest [math]\displaystyle{ (s,v) }[/math]-path and [math]\displaystyle{ (v,w) }[/math]).
Remark: Node labels [math]\displaystyle{ d }[/math] that fulfill the valid distance property need not be distances.
Standard distance update: In all common shortest-paths algorithms, an attribute [math]\displaystyle{ d_s(v) }[/math] is maintained for each [math]\displaystyle{ v\in V }[/math]. This attribute always holds the length of some [math]\displaystyle{ (s,v) }[/math]-path and should be the true distance from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math] on termination. In virtually all standard algorithms, the following update operation is the (only) operation to update [math]\displaystyle{ d }[/math]-values:
- Choose some arc [math]\displaystyle{ (v,w)\in A }[/math].
- If [math]\displaystyle{ (v,w) }[/math] violates the valid distance property, that is [math]\displaystyle{ d_s(w)\gt d_s(v)+\ell(v,w) }[/math], set [math]\displaystyle{ d_s(w):=d_s(v)+\ell(v,w) }[/math].
Distances along shortest paths
Let [math]\displaystyle{ s\in V }[/math] and for each node [math]\displaystyle{ u\in V }[/math] let [math]\displaystyle{ d(u) }[/math] denote the distance from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ u }[/math] with respect to the arc lengths [math]\displaystyle{ \ell }[/math].
Statement: For an arc [math]\displaystyle{ (v,w) }[/math], it is [math]\displaystyle{ d(w)=d(v)+\ell(v,w) }[/math] if, and only if, [math]\displaystyle{ (v,w) }[/math] is the last arc of some shortest [math]\displaystyle{ (s,w) }[/math]-path.
Proof: First consider the case that [math]\displaystyle{ d(w)=d(v)+\ell(v,w) }[/math]. Then the concatenation of the shortest path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math] and [math]\displaystyle{ (v,w) }[/math] has length [math]\displaystyle{ d(w) }[/math] and is thus shortest.
So, consider the case that [math]\displaystyle{ d(w)\neq d(v)+\ell(v,w) }[/math]. Due to the valid distance property, it is then [math]\displaystyle{ d(w)\lt d(v)+\ell(v,w) }[/math]. Suppose for a contradiction that some shortest [math]\displaystyle{ (s,w) }[/math]-path is of the form [math]\displaystyle{ p+(v,w) }[/math]. Then [math]\displaystyle{ p }[/math] would have length [math]\displaystyle{ d(w)-\ell(v,w)\lt d(v) }[/math], which contradicts the definition of [math]\displaystyle{ d(v) }[/math].
Reconstruction of a shortest path from the distances
Suppose that for each node [math]\displaystyle{ v\in V }[/math] the distance [math]\displaystyle{ d_\ell(v) }[/math] from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math] is given. For [math]\displaystyle{ t\in V }[/math], a shortest [math]\displaystyle{ (s,t) }[/math]-path [math]\displaystyle{ p }[/math] can be constructed as follows:
- Initialize [math]\displaystyle{ p }[/math] to be empty.
- Set [math]\displaystyle{ w:=t }[/math].
- While [math]\displaystyle{ w\neq s }[/math]:
- Find an arc [math]\displaystyle{ (v,w) }[/math] such that [math]\displaystyle{ d_\ell(w)=d_\ell(v)+\ell(v,w) }[/math].
- Append [math]\displaystyle{ (v,w) }[/math] at the beginning of [math]\displaystyle{ p }[/math].
Constructing shortest-paths arborescences
As said here, all common algorithms for shortest-paths problems apply a stand update operation. This operation may be extended as follows: Each node [math]\displaystyle{ v\in V\setminus\{s\} }[/math] holds one of its incoming arcs as an additional attribute. At the beginning, this attribute is initialized as void (conforming to [math]\displaystyle{ d(v)=+\infty }[/math]). Whenever the standard update operation is applied to some arc [math]\displaystyle{ (v,w) }[/math], [math]\displaystyle{ (v,w) }[/math] becomes the incoming arc of [math]\displaystyle{ w }[/math].
Statement: Suppose all cycles have strictly positive lengths. On termination of the shortest-path algorithm, the chosen arcs forms a spanning arborescence rooted at [math]\displaystyle{ s }[/math]. For each [math]\displaystyle{ v\in V }[/math], the path in this arborescence is a shortest [math]\displaystyle{ (s,v) }[/math]-path.
Proof: First we show [math]\displaystyle{ d(w)=d(v)+\ell(v,w) }[/math] for each chosen arc [math]\displaystyle{ (v,w)\in A }[/math] on termination. Since [math]\displaystyle{ (v,w) }[/math] is chosen, [math]\displaystyle{ (v,w) }[/math] is the last arc over which [math]\displaystyle{ d(w) }[/math] was updated in the algorithm. At this moment, we indeed have [math]\displaystyle{ d(w)=d(v)+\ell(v,w) }[/math]. As [math]\displaystyle{ d }[/math]-values never increase, [math]\displaystyle{ d(w)\lt d(v)+\ell(v,w) }[/math] is not possible on termination. On the other hand, [math]\displaystyle{ d(w)\gt d(v)+\ell(v,w) }[/math] violates the valid distance property.
By construction, the node [math]\displaystyle{ s }[/math] has indegree zero and all other nodes have indegree one. There cannot be a cycle [math]\displaystyle{ v_1-v_2-\cdots v_k-v_1 }[/math] because this would imply [math]\displaystyle{ d(v_1)=d(v_k)+\ell(v_k,v_1)=d(v_{k-1})+\ell(v_{k-1},v_k)+\ell(v_k,v_1)=\cdots=d(v_1)+\ell(v_k,v_1)+\cdots+\ell(v_1,v_2)\gt d(v_1) }[/math]. In summary, the claim is proved.