Shortest paths by repeated squaring

Algorithmic problem: All pairs shortest paths

Prerequisites: None

Type of algorithm: loop

1. A distance-valued [math]\displaystyle{ (n \times n) }[/math]-matrix [math]\displaystyle{ M }[/math], where [math]\displaystyle{ n = |V| }[/math]. The eventual contents of [math]\displaystyle{ M }[/math] will be returned as the result of the algorithm.
2. A [math]\displaystyle{ (n \times n) }[/math]-matrix [math]\displaystyle{ M }[/math] such that [math]\displaystyle{ M_0(v,w) }[/math], if [math]\displaystyle{ (v,w) \in A }[/math], and [math]\displaystyle{ M_0(v,w)=+\infty }[/math], otherwise.

Auxilliary data:

Abstract view

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

Variant: [math]\displaystyle{ i }[/math] increases by [math]\displaystyle{ 1 }[/math].

Break condition: It is [math]\displaystyle{ \lceil log_2 |V| \rceil }[/math].

Induction basis

Abstract view: Initiallized [math]\displaystyle{ M }[/math] by setting

• [math]\displaystyle{ M(v,w) = 0 }[/math] for all [math]\displaystyle{ v \in V }[/math],
• [math]\displaystyle{ M(v,w) = l(v,w) }[/math] for [math]\displaystyle{ (v,w) \in A }[/math] and
• [math]\displaystyle{ M(v,w) = +\infty }[/math] otherwise.

Implementation: Obvious.

Proof: Nothing to show.

Induction step

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

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 [math]\displaystyle{ |V| }[/math] nodes.

Complexity

Statement: The asymptotic complexity is [math]\displaystyle{ \Theta(n^3 log(n)) }[/math] in the best and worst case.

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