# Shortest paths by repeated squaring

Algorithmic problem: All pairs shortest paths

Prerequisites: None

Type of algorithm: loop

1. A distance-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 $(n \times n)$-matrix $M$ such that $M_0(v,w)$, if $(v,w) \in A$, and $M_0(v,w)=+\infty$, otherwise.

Auxilliary data:

## Abstract view

Invariant: After $i \ge 0$ iterations, it is $M=M_0^{2i}$, where powers of a matrix are defined as Path.

Variant: $i$ increases by $1$.

Break condition: It is $\lceil log_2 |V| \rceil$.

## Induction basis

Abstract view: Initiallized $M$ by setting

• $M(v,w) = 0$ for all $v \in V$,
• $M(v,w) = l(v,w)$ for $(v,w) \in A$ and
• $M(v,w) = +\infty$ otherwise.

Implementation: Obvious.

Proof: Nothing to show.

## Induction step

Abstract view: For all $v, w \in V$, set $M(v,w) := min \{ M(v,w), min \{ M(v,u) + M(u,w) | u \in V \setminus_{ \{v,w\} } \} \}$.

Implementation: Obvious.

Correctness: Maintenance of the invariant is obvious. The claim now follows from the explanations of powers of the distance matrix as Path and from the fact that a shortest path cannot have more than $|V|$ nodes.

## Complexity

Statement: The asymptotic complexity is $\Theta(n^3 log(n))$ in the best and worst case.

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