# 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\geq 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) := +\infty$, if $v\neq 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 $\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 $\Theta (n)$ steps.