All pairs shortest paths: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(9 intermediate revisions by 2 users not shown)
Line 1: Line 1:
== Input ==
== Input ==


# A directed Graph <math>G = (V,A)</math>
# A [[Basic graph definitions|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 ==
== Output ==


For each pair <math>(v,w) \in A</math> with <math> v,w \in V</math>, the length <math>\Delta(v,w)</math> of a shortest <math>(v,w)</math>-path in <math>G</math> with respect to <math>l</math>.
For each pair <math>(v,w) \in A</math> with <math> v,w \in V</math>:
# The length <math>\Delta(v,w)</math> of a shortest <math>(v,w)</math>-path in <math>G</math> with respect to <math>\ell</math> among all paths that have at most <math>|V|</math> arcs.
# The last arc (pointing to <math>w</math>) of one of these paths.
 
'''Remark:'''
# Obviously, if no <math>(v,w)</math>-path meets any negative cycle, a shortest path exists, and at least one shortest path is [[Basic graph definitions#Paths|simple]]  (because such a path may only contain cycles of zero total length, which may be removed). This path has at most <math>|V|-1</math> arcs. On the other hand, if there are negative cycles, there is, evidently, at least one simple negative cycle. A simple cycle has at most <math>|V|</math> arcs. Therefore, the distance from <math>v</math> to <math>w</math> in the output is negative. Of course, the case <math>v=w</math> is included. The nodes <math>v\in V</math> with negative distance <math>v\rightarrow v</math> are exactly the nodes on negative simple cycles.
# The path (or negative cycle) itself may be easily reconstructed backwards along the incoming arcs (output #2).


== Complexity ==
== Complexity ==
Line 14: Line 20:
# [[Floyd-Warshall]]
# [[Floyd-Warshall]]
# [[Bellman-Ford]]
# [[Bellman-Ford]]
# [[Shortest oaths by repeated squaring]] (varian of Bellman-Ford)
# [[Shortest paths by repeated squaring]] (variant of Bellman-Ford)

Latest revision as of 12:56, 22 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]

Output

For each pair [math]\displaystyle{ (v,w) \in A }[/math] with [math]\displaystyle{ v,w \in V }[/math]:

  1. 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{ \ell }[/math] among all paths that have at most [math]\displaystyle{ |V| }[/math] arcs.
  2. The last arc (pointing to [math]\displaystyle{ w }[/math]) of one of these paths.

Remark:

  1. Obviously, if no [math]\displaystyle{ (v,w) }[/math]-path meets any negative cycle, a shortest path exists, and at least one shortest path is simple (because such a path may only contain cycles of zero total length, which may be removed). This path has at most [math]\displaystyle{ |V|-1 }[/math] arcs. On the other hand, if there are negative cycles, there is, evidently, at least one simple negative cycle. A simple cycle has at most [math]\displaystyle{ |V| }[/math] arcs. Therefore, the distance from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math] in the output is negative. Of course, the case [math]\displaystyle{ v=w }[/math] is included. The nodes [math]\displaystyle{ v\in V }[/math] with negative distance [math]\displaystyle{ v\rightarrow v }[/math] are exactly the nodes on negative simple cycles.
  2. The path (or negative cycle) itself may be easily reconstructed backwards along the incoming arcs (output #2).

Complexity

Polynomial

Known algorithms

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