All pairs shortest paths

From Algowiki
Jump to: navigation, search

Input

  1. A directed graph [math]G = (V,A)[/math]
  2. An arc length [math]l(a) \in \mathbb{R}[/math] for each arc [math]a \in A[/math]

Output

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

  1. 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.
  2. The last arc (pointing to [math]w[/math]) of one of these paths.

Remark:

  1. Obviously, if no [math](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]|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.
  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)