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: Consider an algorithm that yields a shortest [math]\displaystyle{ (s,v) }[/math]-path for each node [math]\displaystyle{ v\in V }[/math] whose distance from [math]\displaystyle{ s }[/math] is a real number (that is, neither [math]\displaystyle{ -\infty }[/math] nor [math]\displaystyle{ +\infty }[/math]). 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 part of the statement, first note that the second sentence implies the only-if part of the first sentence, so we do not consider the only-if part of the first sentence. Let [math]\displaystyle{ v }[/math] be a reachable node on a negative cycle. Let [math]\displaystyle{ p }[/math] be a path of chosen arcs that ends in [math]\displaystyle{ v }[/math]; in particular, let [math]\displaystyle{ p }[/math] have a maximal number of arcs among all of these paths. 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] has infinite length, which means [math]\displaystyle{ p }[/math] forms a cycle. To prove that this cycle is negative, let [math]\displaystyle{ v_1-v_2-\cdots-v_k-v_1 }[/math] denote the nodes of this cycle. The length of this cycle cannot be positive because this would yield the immediate contradiction [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]. The length cannot be zero, either, because then 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 is not possible in the standard update. In summary, the second part of the statement is proved.

The third part of the statement is a direct consequence of the first two parts.

(Admissible) node potentials

For each node [math]\displaystyle{ v\in V }[/math], let [math]\displaystyle{ h(v) }[/math] be a real number. For [math]\displaystyle{ a=(v,w)\in A }[/math], set [math]\displaystyle{ \ell^h(a):=\ell(a)-h(v)+h(w) }[/math]. In this context, these values are usually called node potentials. Node potentials are admissible if [math]\displaystyle{ \ell(a)\geq 0 }[/math] for all [math]\displaystyle{ \in A }[/math].

Statement: An [math]\displaystyle{ (s,t) }[/math]-path is shorter than another [math]\displaystyle{ (s,t) }[/math]-path with respect to the arc lengths [math]\displaystyle{ \ell^h }[/math] if, and only if, the same is true for the arc lengths [math]\displaystyle{ \ell }[/math]. In particular, the shortest paths with respect to the arc lengths [math]\displaystyle{ \ell^h }[/math] are exactly the shortest paths with respect to the arc lengths [math]\displaystyle{ \ell }[/math].

Proof: Let [math]\displaystyle{ s=v_1-v_2-\cdots-v_k=t }[/math] be the nodes on an [math]\displaystyle{ (s,t) }[/math]-path. The length of this path with respect to [math]\displaystyle{ \ell^h }[/math] is then [math]\displaystyle{ \sum_{i=1}^{k-1}\ell^h(v_i,v_{i+1})=\sum_{i=1}^{k-1}\left[\ell(v_i,v_{i+1})-h(v_{i+1})+h(v_i)\right]=\sum_{i=1}^{k-1}\ell(v_i,v_{i+1})-h(s)+h(t) }[/math]. In other words, the lengths of an [math]\displaystyle{ (s,t) }[/math]-path with respect to [math]\displaystyle{ \ell^h }[/math] and [math]\displaystyle{ \ell }[/math], respectively, differ by a constant addend, [math]\displaystyle{ h(t)-h(s) }[/math].

Remark: Admissible node potentials allow efficient algorithms such as Dijkstra's, which require nonnegative arc lengths.