Floyd-Warshall: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
Line 6: Line 6:
<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://google.de Openlearnware]</div>
<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://google.de Openlearnware]</div>
</div>
</div>
== Abstract View ==


'''Algorithmic problem:''' [[All pairs shortest paths]]
'''Algorithmic problem:''' [[All pairs shortest paths]]
Line 18: Line 19:
# C An ordering of all nodes, that is, <math>V = \{u_1, \ldots ,u_n\}</math>
# C An ordering of all nodes, that is, <math>V = \{u_1, \ldots ,u_n\}</math>


== Abstract View ==
'''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>.
'''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>.


'''Varian:''' <math>i</math> increases by <math>1</math>.
'''Variant:''' <math>i</math> increases by <math>1</math>.


'''Break condition:''' It is <math>i=n</math>
'''Break condition:''' It is <math>i=n</math>

Revision as of 08:51, 20 July 2015

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]\displaystyle{ n = |V| }[/math]
  2. A distance-valued [math]\displaystyle{ (n \times n) }[/math] matrix [math]\displaystyle{ M }[/math]
  3. C An ordering of all nodes, that is, [math]\displaystyle{ V = \{u_1, \ldots ,u_n\} }[/math]

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

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

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

Break condition: It is [math]\displaystyle{ i=n }[/math]

Induction basis

Abstract view: [math]\displaystyle{ \forall v,w \in V }[/math] we set

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

Implementation: Obvious.

Proof: Nothing to show.

Induction step

Abstract view: Bring $v_i$ into the game.

Implementation: For all $v,w\in V$: If [math]\displaystyle{ M(v, }[/math]

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

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

Complexity

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

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