Bellman-Ford: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(6 intermediate revisions by 2 users not shown)
Line 1: Line 1:
__NOTOC__
[[Category:Videos]]
[[Category:Checkup]]
[[Category:Algorithm]]
[[Category:Algorithm]]
[[Category:Main Algorithm]]
[[Category:Main Algorithm]]
{{#ev:youtube|https://www.youtube.com/watch?v=3_zqU5GWo4w|500|right|All pairs shortest paths Bellman-Ford|frame}}
==General information==
==General information==
'''Algorithmic problem:''' [[All pairs shortest paths]]
'''Algorithmic problem:''' [[All pairs shortest paths]]
Line 11: Line 11:


'''Auxiliary data:'''
'''Auxiliary data:'''
# 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 real-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 real-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.
 
'''Notation:'''
On this page, <math>M^i</math> refers to the contents of <math>M</math> after <math>i\geq 0</math> iterations.


==Abstract view==
==Abstract view==
Line 34: Line 37:
'''Implementation:''' Obvious.
'''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.
'''Correctness:''' Follows from the fact that a shortest path cannot have more than <math>|V|-1</math> arcs.


==Complexity==
==Complexity==

Latest revision as of 22:51, 19 June 2015

All pairs shortest paths Bellman-Ford

General information

Algorithmic problem: All pairs shortest paths

Prerequisites:

Type of algorithm: loop

Auxiliary data:

  1. A real-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.
  2. A real-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.

Notation: On this page, [math]\displaystyle{ M^i }[/math] refers to the contents of [math]\displaystyle{ M }[/math] after [math]\displaystyle{ i\geq 0 }[/math] iterations.

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

  1. [math]\displaystyle{ M^0 (v,v):= L(v,v) := 0 }[/math];
  2. [math]\displaystyle{ M^0 (v,w):= L(v,w) := \ell (v,w) }[/math] if [math]\displaystyle{ (v,w)\in A }[/math];
  3. [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,u) + L(u,w) \mid u \in V \} }[/math].

(Note that [math]\displaystyle{ u=v }[/math] is included, 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 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.