From Algowiki
Jump to: navigation, search

Abstract View

Algorithmic problem: All pairs shortest paths

Prerequisites: None

Type of algorithm: loop

Auxilliary data:

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

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

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

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

Break condition: It is [math]i=n[/math]

Induction basis

Abstract view: For all [math]v,w \in V[/math] we set

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

Implementation: Obvious.

Proof: Nothing to show.

Induction step

Abstract view: Bring [math]v_i[/math] into the game.

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

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

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


Statement: [math]\mathcal{O}(n^3)[/math]

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