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 cycles of nonpositive lengths 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: 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(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.

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.

Now it remains to show that the incoming arcs form an arborescence as described in the statement provided no negative cycles are reachable. We have seen that, in this case, the node [math]\displaystyle{ s }[/math] has indegree zero. By construction, all other nodes have indegree one. There cannot be a cycle [math]\displaystyle{ v_1-v_2-\cdots v_k-v_1 }[/math] of chosen arcs because this cycle ist strictly positive, 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)\gt d(v_1) }[/math]. In summary, the claim is proved.