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. In that restricted version, the subpath property 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 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 shortest [math]\displaystyle{ (s,v) }[/math] with [math]\displaystyle{ (v,w) }[/math] appended).

== Distances along shortest paths

Reconstruction of a shortest paths

From distances: Suppose that for each node [math]\displaystyle{ v\in V }[/math] the distance 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 can be constructed as follows:

1. Set [math]\displaystyle{ v:= }[/math].
2. While [math]\displaystyle{ v\neq s }[/math]:
   1. Find an arc [math]\displaystyle{ (w,v) }[/math]