Bellman-Ford

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 $(n\times n)$ matrix $M$, where $n=|V|$. The eventual contents of $M$ will be returned as the result of the algorithm.
2. A real-valued $(n\times n)$ matrix $L$, where $n=|V|$. This matrix represents the graph and the arc lengths and will not be changed throughout the algorithm.

Notation: On this page, $M^i$ refers to the contents of $M$ after $i\ge 0$ iterations.

Abstract view

Invariant: After $i\ge 0$ iterations, $M^i(v,w)$ contains the length of a shortest $(v,w)$-path with at most $i+1$ arcs (for all $v,w\in V$).

Variant: $i$ increases by 1.

Break condition: $i=n-1$.

Induction basis

Abstract view: For all $v,w\in V$, we set

1. $M^0(v,v):=L(v,v):=0$;
2. $M^0(v,w):=L(v,w):=\ell (v,w)$ if $(v,w)\in A$;
3. $M^0(v,w):=L(v,w):=+\mathrm{\infty }$, if $v\ne w$ and $(v,w)\notin A$.

Induction step

Abstract view: For all $v,w\in V$, we set $M^{i+1}(v,w):=min\{M^i(v,u)+L(u,w)\mid u\in V\}$.

(Note that $u=v$ is included, so the right-hand side is identical to $min\{M^i(v,w),min\{M^i(v,u)+L(u,w)\mid u\in V\}\}$.)

Implementation: Obvious.

Correctness: Follows from the fact that a shortest path cannot have more than $|V|-1$ arcs.

Complexity

Statement: The asymptotic complexity is $\mathrm{\Theta }(n^4)$ in the best and worst case.

Proof: The main loop terminates after $n-1$ iterations. In each iteration of this loop, we update all $n^2$ matrix entries, and computing one update value requires $\mathrm{\Theta }(n)$ steps.