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
フィボナッチヒープとダイクストラ,ベルマン・フォードを使うという,実装はハードそう.
疎なグラフに対しては有効という話.
作成者 Toru Mano
最終更新時刻 2022-02-27 (a2c95c7)