Shortest paths by repeated squaring
Algorithmic problem: All pairs shortest paths
Prerequisites: None
Type of algorithm: loop
- 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.
- 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.