P179: Enumeration of all all to all shortest paths in a graph

P179: Enumeration of all all to all shortest paths in a graph

Input:

A graph $G = (V, E)$.

Output:

All shortest paths in $G$.

Complexity:

$O(M(|V|) + |V|^2)$ total time.

Comment:

All pair shortest paths. $M(n)$ is the time complexity of the best algorithm for $n\times n$ matrix multiplication.

Reference:

[Watanabe1981] (Bibtex)