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.

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