All pairs shortest paths

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], 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.

Remark: Obviously, a shortest path that contains no negative cycle is simple, so it has at most [math]\displaystyle{ |V|-1 }[/math] arcs. If there are negative cycles, there are pairs [math]\displaystyle{ v,w\in V }[/math] for which the lengths of all [math]\displaystyle{ (v,w) }[/math] is unbounded from below. At least one of these paths runs exactly once through one simple negative cycle and For each such pair, there is a negative

Complexity

Polynomial

Known algorithms

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