Basics of shortest paths: Difference between revisions
Line 70: | Line 70: | ||
== Constructing shortest-paths arborescences == | == Constructing shortest-paths arborescences == | ||
As said [[#Valid distance property|here]], all common algorithms for shortest-paths problems apply a standard update operation. This operation may be extended as follows ( | As said [[#Valid distance property|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>s</math>): Each node <math>v\in V</math> holds one of its incoming arcs as an additional attribute: | ||
# ''Initialization'': This attribute is initialized as void for <math>s</math> and for all <math>v</math> for which <math>d(v)</math> is initialized as <math>d(v)=+\infty</math>). Some algorithms (or variants of algorithms) initially set <math>d(v)=\ell(s,v)</math> for all <math>(s,v)\in A</math>. In this case, <math>(s,v)</math> is the initial incoming arc of <math>v</math>. | # ''Initialization'': This attribute is initialized as void for <math>s</math> and for all <math>v</math> for which <math>d(v)</math> is initialized as <math>d(v)=+\infty</math>). Some algorithms (or variants of algorithms) initially set <math>d(v)=\ell(s,v)</math> for all <math>(s,v)\in A</math>. In this case, <math>(s,v)</math> is the initial incoming arc of <math>v</math>. | ||
# ''Update'': Whenever the standard update operation is applied to some arc <math>(v,w)</math>, <math>(v,w)</math> becomes the incoming arc of <math>w</math>. | # ''Update'': Whenever the standard update operation is applied to some arc <math>(v,w)</math>, <math>(v,w)</math> becomes the incoming arc of <math>w</math>. |
Revision as of 10:08, 4 December 2014
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].
- The length of an ordinary path (incl. ordinary cycles) is the sum of the lengths of all arcs on this path.
- 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.
- If the length of an ordinary or generalized cycle is negative, this cycle is called a negative cycle.
- 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.
- The distance from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ t }[/math] is:
- [math]\displaystyle{ +\infty }[/math] if no [math]\displaystyle{ (s,t) }[/math]-path exists;
- [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);
- the length of a shortest [math]\displaystyle{ (s,t) }[/math]-path in all other cases.
Remarks:
- In this context, undirected graphs are usually regarded as symmetric directed graphs such that two mutually opposite arcs have the same length.
- 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:
- Choose some arc [math]\displaystyle{ (v,w)\in A }[/math].
- 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:
- Initialize [math]\displaystyle{ p }[/math] to be empty.
- Set [math]\displaystyle{ w:=t }[/math].
- While [math]\displaystyle{ w\neq s }[/math]:
- Find an arc [math]\displaystyle{ (v,w) }[/math] such that [math]\displaystyle{ d_s(w)=d_s(v)+\ell(v,w) }[/math].
- Append [math]\displaystyle{ (v,w) }[/math] at the beginning of [math]\displaystyle{ p }[/math].
- Set [math]\displaystyle{ w:=v }[/math].
Constructing shortest-paths arborescences
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:
- 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].
- 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 incoming arc of [math]\displaystyle{ s }[/math] is void if, and only if, [math]\displaystyle{ s }[/math] is not on any negative cycle. In this case, the chosen arcs forms a spanning arborescence rooted at [math]\displaystyle{ s }[/math]. For each [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 }[/math]-values never increase, [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.
By construction, the node [math]\displaystyle{ s }[/math] has indegree zero and all other nodes have indegree one. There cannot be a cycle [math]\displaystyle{ v_1-v_2-\cdots v_k-v_1 }[/math] because this would imply [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_k,v_1)+\cdots+\ell(v_1,v_2)\gt d(v_1) }[/math]. In summary, the claim is proved.