Johonson’s algorithm (疎なグラフに対する全対全最短路アルゴリズム)

全対全最短路はふつうにWarshall Floydを使うと O(V^3) だけど

Johonson’s algorithmをつかえば,O(V^2 log V + VE )でできる.

http://en.wikipedia.org/wiki/Johnson%27s_algorithm

フィボナッチヒープとダイクストラ,ベルマン・フォードを使うという,実装はハードそう.

疎なグラフに対しては有効という話.