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].

1. The length of an ordinary path (incl. ordinary cycles) is the sum of the lengths of all arcs on this path.
2. 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.
3. If the length of an ordinary or generalized cycle is negative, this cycle is called a negative cycle.
4. 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.
5. The distance from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] is:
   1. [math]\displaystyle{ +\infty }[/math] if no [math]\displaystyle{ (s,t) }[/math]-path exists;
   2. [math]\displaystyle{ -\infty }[/math] if there is a negative cycle on some [math]\displaystyle{ (s,t) }[/math]-path (note that paths are not assumed to be simple);
   3. the length of a shortest [math]\displaystyle{ (s,t) }[/math]-path in all other cases.

Remarks:

1. In this context, undirected graphs are usually regarded as symmetric directed graphs such that two mutually opposite arcs have the same length.
2. 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. On the other hand, if a node is on a negative cycle, its distance to itself is [math]\displaystyle{ -\infty }[/math].

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(w)\leq d(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(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:

1. Choose some arc [math]\displaystyle{ (v,w)\in A }[/math].
2. If [math]\displaystyle{ (v,w) }[/math] violates the valid distance property, that is [math]\displaystyle{ d(w)\gt d(v)+\ell(v,w) }[/math], set [math]\displaystyle{ d(w):=d(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: Suppose there are no negative cycles. 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 some nodes [math]\displaystyle{ s,t\in V }[/math], the distance [math]\displaystyle{ d_s(t) }[/math] from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] with respect to arc lengths [math]\displaystyle{ \ell }[/math] is a real number (that is, neither [math]\displaystyle{ -\infty }[/math] nor [math]\displaystyle{ +\infty }[/math]). Then a shortest [math]\displaystyle{ (s,t) }[/math]-path [math]\displaystyle{ p }[/math] can be constructed as follows:

1. Initialize [math]\displaystyle{ p }[/math] to be empty.
2. Set [math]\displaystyle{ w:=t }[/math].
3. While [math]\displaystyle{ w\neq s }[/math]:
   1. Find an arc [math]\displaystyle{ (v,w) }[/math] such that [math]\displaystyle{ d_s(w)=d_s(v)+\ell(v,w) }[/math].
   2. Append [math]\displaystyle{ (v,w) }[/math] at the beginning of [math]\displaystyle{ p }[/math].
   3. Set [math]\displaystyle{ w:=v }[/math].

Constructing a shortest-paths arborescence or a negative cycle

As said here, all common algorithms for shortest-paths problems apply a standard update operation. This operation may be extended as follows (with the start node denoted by [math]\displaystyle{ s }[/math]). Each node [math]\displaystyle{ v\in V }[/math] holds one of its incoming arcs as an additional attribute:

1. Initialization: This attribute is initialized as void for [math]\displaystyle{ s }[/math] and for all [math]\displaystyle{ v }[/math] for which [math]\displaystyle{ d(v) }[/math] is initialized as [math]\displaystyle{ d(v)=+\infty }[/math]. Some algorithms (or variants of algorithms) initially set [math]\displaystyle{ d(v)=\ell(s,v) }[/math] for all [math]\displaystyle{ (s,v)\in A }[/math]. In this case, [math]\displaystyle{ (s,v) }[/math] is the initial incoming arc of [math]\displaystyle{ v }[/math].
2. Update: 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: On termination, the following statements hold:

1. The incoming arc of [math]\displaystyle{ s }[/math] is void if, and only if, [math]\displaystyle{ s }[/math] is not on any negative cycle.
2. The chosen arcs contain a cycle if, and only if, the reachable nodes contain negative cycles. Each cycle in the chosen arcs is a negative cycle.
3. If the nodes reachable from [math]\displaystyle{ s }[/math] do not contain negative cycles at all, the chosen arcs form an arborescence that is rooted at [math]\displaystyle{ s }[/math] and spans all nodes reachable from [math]\displaystyle{ s }[/math]. For each reachable [math]\displaystyle{ v\in V }[/math], the path from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math] in this arborescence is a shortest [math]\displaystyle{ (s,v) }[/math]-path.

Proof: The algorithm will yield [math]\displaystyle{ d(s)\lt 0 }[/math] if, and only if, [math]\displaystyle{ s }[/math] is on some negative cycle. Exactly in this case will the incoming arc of [math]\displaystyle{ s }[/math] be updated. This proves the first part of the statement.

For the second statement, first let [math]\displaystyle{ v }[/math] be a reachable node on a negative cycle. Let [math]\displaystyle{ p }[/math] be a path of maximal number of chosen arcs that ends in [math]\displaystyle{ v }[/math]. Then [math]\displaystyle{ p }[/math] cannot start at [math]\displaystyle{ s }[/math] because the algorithm will deliver a distance value for [math]\displaystyle{ v }[/math] that is smaller than the true distance. Clearly, [math]\displaystyle{ p }[/math] cannot start at an unreachable node, either. Since an incoming arc is chosen for any other node, [math]\displaystyle{ p }[/math] cannot start anywhere, so [math]\displaystyle{ p }[/math] is a cycle.

For the other direction of the second statement, we first 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. Therefore, at this moment, we indeed have [math]\displaystyle{ d(w)=d(v)+\ell(v,w) }[/math]. As [math]\displaystyle{ d(w) }[/math] changes never again and [math]\displaystyle{ d(v) }[/math] never increases, [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. Now, to prove that there cannot be a cycle [math]\displaystyle{ v_1-v_2-\cdots v_k-v_1 }[/math] of chosen arcs, note that this cycle ist nonnegative, so we obtain [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_1,v_2)+\cdots+\ell(v_k,v_1)\geq d(v_1) }[/math]. If this inequality is strict, [math]\displaystyle{ v_1-v_2-\cdots v_k-v_1 }[/math] would be a negative cycle. On the other hand, if this inequality is an equation, the arc of the cycle that is chosen last had been chosen in a situation in which the distance update of its head is zero, which never occurs in the standard update.

In summary, the second statement is proved. The third statement follows directly.