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

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

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

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

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