Bellman-Ford: Difference between revisions
(Created page with "Category:Algorithm Category:Main Algorithm '''Algorithmic problem:''' All pairs shortest paths '''Prerequisites:''' '''Type of algorithm:''' loop '''Auxiliary data...") |
No edit summary |
||
Line 1: | Line 1: | ||
__NOTOC__ | |||
[[Category:Checkup]] | |||
[[Category:Algorithm]] | [[Category:Algorithm]] | ||
[[Category:Main Algorithm]] | [[Category:Main Algorithm]] | ||
Line 7: | Line 9: | ||
# A [[Paths|distance-valued]] <math>(n \times n)</math> matrix <math>M</math>, where <math>n=|V|</math>. The eventual contents of <math>M</math> will be returned as the result of the algorithm. | # A [[Paths|distance-valued]] <math>(n \times n)</math> matrix <math>M</math>, where <math>n=|V|</math>. The eventual contents of <math>M</math> will be returned as the result of the algorithm. | ||
# A [[Paths|distance-valued]] <math>(n \times n)</math> matrix <math>L</math>, where <math>n=|V|</math>. This matrix represents the graph and the arc lengths and will not be changed throughout the algorithm. It is <math>L=M^1</math> in the terminology of Section "Powers of distance matrices" on [[Paths#Powers of distance matrices|this]] page. | # A [[Paths|distance-valued]] <math>(n \times n)</math> matrix <math>L</math>, where <math>n=|V|</math>. This matrix represents the graph and the arc lengths and will not be changed throughout the algorithm. It is <math>L=M^1</math> in the terminology of Section "Powers of distance matrices" on [[Paths#Powers of distance matrices|this]] page. | ||
==Abstract view== | |||
'''Invariant:''' After <math>i \ge 0</math> iterations, <math>M^i (v,w)</math> contains the length of a shortest <math>(v,w)</math>-path with at most <math>i+1</math> arcs (for all <math>v,w \in V</math>). | |||
'''Variant:''' <math>i</math> increases by 1. | |||
'''Break condition:''' <math>i=n-1</math>. | |||
==Induction basis== | |||
'''Abstract view:''' For all <math>v,w \in V</math>, we set | |||
# <math>M^0 (v,v):= L(v,v) := 0</math>; | |||
# <math>M^0 (v,w):= L(v,w) := \ell (v,w)</math> if <math>(v,w)\in A</math>; | |||
# <math>M^0 (v,w):= L(v,w) := +\infty</math>, if <math>v\neq w</math> and <math>(v,w)\notin A</math>. | |||
==Induction step== | |||
'''Abstract view:''' For all <math>v,w \in V</math>, we set <math>M^{i+1} (v,w) := \min \{ M^i (v,w) + L(u,w) \mid u \in V \}</math>. | |||
(Note that <math>M^i (v,w) + L(u,w) = M^{i+1} (v,w)</math> is one of the arguments over which the minimum is taken, so the right-hand side is identical to <math>\min \{ M^i (v,w), \min \{ M^i (v,u)+ L(u,w) \mid u \in V \} \}</math>.) | |||
'''Implementation:''' Obvious. | |||
'''Correctness:''' Follows from the explanations of [[Paths#Powers of distance matrices|powers of the distance matrix]] and from the fact that a shortest path cannot have more than <math>|V|-1</math> arcs. | |||
==Complexity== | |||
'''Statement:''' The asymptotic complexity is <math>\Theta (n^4)</math> in the best and worst case. | |||
'''Proof:''' The main loop terminates after <math>n-1</math> iterations. In each iteration of this loop, we update all <math>n^2</math> matrix entries, and computing one update value requires <math>\Theta (n)</math> steps. |
Revision as of 10:05, 6 October 2014
Algorithmic problem: All pairs shortest paths Prerequisites: Type of algorithm: loop Auxiliary data:
- A distance-valued [math]\displaystyle{ (n \times n) }[/math] matrix [math]\displaystyle{ M }[/math], where [math]\displaystyle{ n=|V| }[/math]. The eventual contents of [math]\displaystyle{ M }[/math] will be returned as the result of the algorithm.
- A distance-valued [math]\displaystyle{ (n \times n) }[/math] matrix [math]\displaystyle{ L }[/math], where [math]\displaystyle{ n=|V| }[/math]. This matrix represents the graph and the arc lengths and will not be changed throughout the algorithm. It is [math]\displaystyle{ L=M^1 }[/math] in the terminology of Section "Powers of distance matrices" on this page.
Abstract view
Invariant: After [math]\displaystyle{ i \ge 0 }[/math] iterations, [math]\displaystyle{ M^i (v,w) }[/math] contains the length of a shortest [math]\displaystyle{ (v,w) }[/math]-path with at most [math]\displaystyle{ i+1 }[/math] arcs (for all [math]\displaystyle{ v,w \in V }[/math]).
Variant: [math]\displaystyle{ i }[/math] increases by 1.
Break condition: [math]\displaystyle{ i=n-1 }[/math].
Induction basis
Abstract view: For all [math]\displaystyle{ v,w \in V }[/math], we set
- [math]\displaystyle{ M^0 (v,v):= L(v,v) := 0 }[/math];
- [math]\displaystyle{ M^0 (v,w):= L(v,w) := \ell (v,w) }[/math] if [math]\displaystyle{ (v,w)\in A }[/math];
- [math]\displaystyle{ M^0 (v,w):= L(v,w) := +\infty }[/math], if [math]\displaystyle{ v\neq w }[/math] and [math]\displaystyle{ (v,w)\notin A }[/math].
Induction step
Abstract view: For all [math]\displaystyle{ v,w \in V }[/math], we set [math]\displaystyle{ M^{i+1} (v,w) := \min \{ M^i (v,w) + L(u,w) \mid u \in V \} }[/math].
(Note that [math]\displaystyle{ M^i (v,w) + L(u,w) = M^{i+1} (v,w) }[/math] is one of the arguments over which the minimum is taken, so the right-hand side is identical to [math]\displaystyle{ \min \{ M^i (v,w), \min \{ M^i (v,u)+ L(u,w) \mid u \in V \} \} }[/math].)
Implementation: Obvious.
Correctness: Follows from the explanations of powers of the distance matrix and from the fact that a shortest path cannot have more than [math]\displaystyle{ |V|-1 }[/math] arcs.
Complexity
Statement: The asymptotic complexity is [math]\displaystyle{ \Theta (n^4) }[/math] in the best and worst case.
Proof: The main loop terminates after [math]\displaystyle{ n-1 }[/math] iterations. In each iteration of this loop, we update all [math]\displaystyle{ n^2 }[/math] matrix entries, and computing one update value requires [math]\displaystyle{ \Theta (n) }[/math] steps.