All pairs shortest paths

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)