Bellman-Ford

From Algowiki
Jump to: navigation, search
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](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.
  2. 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

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

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

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