All pairs shortest paths: Difference between revisions
Jump to navigation
Jump to search
Dkratschmann (talk | contribs) (Created page with "== Input == * A directed Graph <math>G = (V,A)</math> * An arc length <math>l(a) \in \mathbb{R}</math> for each arc <math>a \in A</math> == Ouptut == For each pair <math>(v...") |
Dkratschmann (talk | contribs) No edit summary |
||
| Line 1: | Line 1: | ||
== Input == | == Input == | ||
# A directed Graph <math>G = (V,A)</math> | |||
# An arc length <math>l(a) \in \mathbb{R}</math> for each arc <math>a \in A</math> | |||
== Ouptut == | == Ouptut == | ||
| Line 12: | Line 12: | ||
== Known algorithms == | == Known algorithms == | ||
# [[Floyd-Warshall]] | |||
# [[Bellman-Ford]] | |||
# [[Shortest oaths by repeated squaring]] (varian of Bellman-Ford) | |||
Revision as of 13:59, 4 October 2014
Input
- A directed Graph [math]\displaystyle{ G = (V,A) }[/math]
- An arc length [math]\displaystyle{ l(a) \in \mathbb{R} }[/math] for each arc [math]\displaystyle{ a \in A }[/math]
Ouptut
For each pair [math]\displaystyle{ (v,w) \in A }[/math] with [math]\displaystyle{ v,w \in V }[/math], the length [math]\displaystyle{ \Delta(v,w) }[/math] of a shortest [math]\displaystyle{ (v,w) }[/math]-path in [math]\displaystyle{ G }[/math] with respect to [math]\displaystyle{ l }[/math].
Complexity
Polynomial
Known algorithms
- Floyd-Warshall
- Bellman-Ford
- Shortest oaths by repeated squaring (varian of Bellman-Ford)