All pairs shortest paths: Difference between revisions

From Algowiki
Jump to navigation Jump to search
(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...")
 
No edit summary
Line 1: Line 1:
== Input ==
== Input ==


* A directed Graph <math>G = (V,A)</math>
# 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>
# 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]]
# [[Floyd-Warshall]]
* [[Bellman-Ford]]
# [[Bellman-Ford]]
* [[Shortest oaths by repeated squaring]] (varian of Bellman-Ford)
# [[Shortest oaths by repeated squaring]] (varian of Bellman-Ford)

Revision as of 13:59, 4 October 2014

Input

  1. A directed Graph [math]\displaystyle{ G = (V,A) }[/math]
  2. 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

  1. Floyd-Warshall
  2. Bellman-Ford
  3. Shortest oaths by repeated squaring (varian of Bellman-Ford)