Shortest paths by repeated squaring

From Algowiki
Jump to: navigation, search

Algorithmic problem: All pairs shortest paths

Prerequisites: None

Type of algorithm: loop

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

Auxilliary data:

Abstract view

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

Variant: [math]i[/math] increases by [math]1[/math].

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

Induction basis

Abstract view: Initiallized [math]M[/math] by setting

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

Implementation: Obvious.

Proof: Nothing to show.

Induction step

Abstract view: For all [math]v, w \in V[/math], set [math]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]|V| [/math] nodes.


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

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