Floyd-Warshall: Difference between revisions
Jump to navigation
Jump to search
Dkratschmann (talk | contribs) No edit summary |
No edit summary |
||
| (13 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
== Abstract View == | |||
'''Algorithmic problem:''' [[All pairs shortest paths]] | '''Algorithmic problem:''' [[All pairs shortest paths]] | ||
| Line 7: | Line 9: | ||
'''Auxilliary data:''' | '''Auxilliary data:''' | ||
# A constant representing the number of node: <math>n = |V|</math> | # A constant representing the number of node: <math>n = |V|</math> | ||
# A | # A real-valued <math>(n \times n)</math> matrix <math>M</math> | ||
# | # 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>. | '''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> | '''Break condition:''' It is <math>i=n</math> | ||
== Induction basis == | == Induction basis == | ||
'''Abstract view:''' <math> | '''Abstract view:''' For all <math>v,w \in V</math> we set | ||
# <math>M(v,v):=0, \forall v \in V</math> | # <math>M(v,v):=0, \forall v \in V</math> | ||
# <math>M(v,w):=l(v,w), (v,w) \in A</math> | # <math>M(v,w):=l(v,w), (v,w) \in A</math> | ||
| Line 35: | Line 32: | ||
== Induction step == | == Induction step == | ||
'''Abstract view:''' | '''Abstract view:''' Bring <math>v_i</math> into the game. | ||
'''Implementation:''' | '''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>. | '''Correctness:''' Let <math>p</math> denote a shoortest <math>(v,w</math>-path subject to the constraint that all [[Basic graph definitions#Paths|internal nodes]] are taken from <math>\{u_1, \ldots, u_n \}</math>. | ||
# 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. | # 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. | ||
# 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. | # On the other hand, suppose <math>p</math> does contain <math>u_i</math>. Due to the [[basics of shortest paths#Subpath property of shortest paths|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. | ||
== Complexity == | == Complexity == | ||
Latest revision as of 09:28, 24 May 2022
Abstract View
Algorithmic problem: All pairs shortest paths
Prerequisites: None
Type of algorithm: loop
Auxilliary data:
- A constant representing the number of node: [math]\displaystyle{ n = |V| }[/math]
- A real-valued [math]\displaystyle{ (n \times n) }[/math] matrix [math]\displaystyle{ M }[/math]
- 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: For all [math]\displaystyle{ v,w \in V }[/math] we set
- [math]\displaystyle{ M(v,v):=0, \forall v \in V }[/math]
- [math]\displaystyle{ M(v,w):=l(v,w), (v,w) \in A }[/math]
- [math]\displaystyle{ M(v,w):= +\infty }[/math], otherwise
Implementation: Obvious.
Proof: Nothing to show.
Induction step
Abstract view: Bring [math]\displaystyle{ v_i }[/math] into the game.
Implementation: For all [math]\displaystyle{ v,w\in V }[/math], set [math]\displaystyle{ M^{i+1}(v,w):=\min\{M^i(v,w),M^i(v,u_i)+M^i(u_i,w)\} }[/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].
- 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.
- 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.