# Floyd-Warshall

## Abstract View

Algorithmic problem: All pairs shortest paths

Prerequisites: None

Type of algorithm: loop

Auxilliary data:

1. A constant representing the number of node: $n = |V|$
2. A real-valued $(n \times n)$ matrix $M$
3. An ordering of all nodes, that is, $V = \{u_1, \ldots ,u_n\}$

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

Invariant: After $i \ge 0$ iterations, for $v,w \in V$, $M(v,w)$ is the length of a shortest $(v,w)$-path subject to the constraint that all internal nodes of the path belong to $\{u_1, \ldots , u_i\}$.

Variant: $i$ increases by $1$.

Break condition: It is $i=n$

## Induction basis

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

1. $M(v,v):=0, \forall v \in V$
2. $M(v,w):=l(v,w), (v,w) \in A$
3. $M(v,w):= +\infty$, otherwise

Implementation: Obvious.

Proof: Nothing to show.

## Induction step

Abstract view: Bring $v_i$ into the game.

Implementation: For all $v,w\in V$, set $M^{i+1}(v,w):=\min\{M^i(v,w),M^i(v,u_i)+M^i(u_i,w)\}$.

Correctness: Let $p$ denote a shoortest $(v,w$-path subject to the constraint that all internal nodes are taken from $\{u_1, \ldots, u_n \}$.

1. If $p$ does not contain $u_i$, $p$ is even a shortest $(v,w)$-path such that all internal nodes are taken from $\{u_1, \ldots , u_{i-1} \}$. In this case, the induction hypothesis implies that the value of $M(v,w)$ immediately before the i-th iteration equals the length of $p$. Clearly, the i-th iteration does not change the value of $M(v,w)$ in this case.
2. On the other hand, suppose $p$ does contain $u_i$. Due to the prefix property, the segment of $p$ from $v$ to $u_i$ and from $u_i$ to $w$ are a shortest $(v,u_i)$-path and a shortest $(u_i,w)$-path, respectively, subject to the constraint that all internal nodes are from $\{u_1, \ldots , u_{i-1} \}$. The induction hypothesis implies that tehese lengths equal the values $M(v,u_i)$ and $M(u_i, w)$, respectively.

## Complexity

Statement: $\mathcal{O}(n^3)$

Proof: The overall loop has $n$ iterations. In each iteration, we update all $n^2$ matrix entities. Each update requires a constant number of steps.