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]:
   1. 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.
   2. The distance from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] is the length of a shortest [math]\displaystyle{ (s,t) }[/math]-path.

Remarks:

1. In this context, undirected graphs are usually regarded as symmetric directed graphs such that two 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.

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 subpaths at the beginning of a shortest path are considered. That restricted version is called the prefix property.

Valid distance property

Let [math]\displaystyle{ s\in V }[/math] and for each node [math]\displaystyle{ u\in V }[/math] let [math]\displaystyle{ d_\ell(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 [math]\displaystyle{ (v,w)\in A }[/math], it is [math]\displaystyle{ d_\ell(w)\leq d_\ell(v)+\ell(v,w) }[/math].

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.

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_\ell(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_\ell(w)=d_\ell(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_\ell(w)=d_\ell(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_\ell(w) }[/math] and is thus shortest.

So, consider the case that [math]\displaystyle{ d_\ell(w)\neq d_\ell(v)+\ell(v,w) }[/math]. Due to the valid distance property, it is then [math]\displaystyle{ d_\ell(w)\lt d_\ell(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_\ell(w)-\ell(v,w)\lt d_\ell(v) }[/math], which contradicts the definition of [math]\displaystyle{ d_\ell(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:

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_\ell(w)=d_\ell(v)+\ell(v,w) }[/math].
   2. Append [math]\displaystyle{ (v,w) }[/math] at the beginning of [math]\displaystyle{ p }[/math].

Shortest-paths arborescence

Statement:

Remark: This remark applies to algorithms for shortest-paths problems of all types:

1. Single-source single-target shortest paths
2. Single-source shortest paths
3. All-pairs shortest paths

Whenever the current distance value of a node is updated in a sh