最短経路アルゴリズムまとめ

今日、グラフアルゴリズム勉強会をした。

第一弾は、最短経路問題を解くためのアルゴリズムについて。

以下まとめ。

	Bellman-Ford	Dijkstra(matrix)	Dijkstra(list)	Warshall-Floyd
Applicable Problem	単一始点最短路問題	単一始点最短距離問題	単一始点最短距離問題	全頂点対最短経路問題
Input Data Form	隣接リスト	隣接行列	隣接行列	隣接行列
Idea	・すべての距離を毎回更新	・確定した接点に接続する接点の距離のみ更新	・priority_queueを用いて確定接点の探索を高速化 ・暫定距離の更新も実在する枝の数だけで実施	・逐次通過可能な接点集合を増加させながら解く
Calculation Amount	・1回のループではE本の枝を走査 ・負の閉路が含まれないければループは高々V-1回で終わる（最短パスに含まれる頂点数は最高でもV-1であるため） ・O(E * V)	・外側のループ一回につき一つの接点が確定 ・ループ内部では、最小値検索、V個の距離更新を行う ・O(V^2)	・値の更新はO(E)で実施できる ・値の取り出しはO(logV)で実行でき、O(E)回程度実行される ・O(ElogV)	・通過できる接点は1つずつ増やす ・隣接行列の値を毎回すべて更新する ・O(V^3)
Feature	・負の辺が含まれていても解ける ・負の閉路がある場合は更新が無限に続くため解けない。 （※無効グラフの場合は辺も閉路になるので注意） ・上記の性質を利用すれば負の閉路を検出できる	・負の辺が含まれている場合は解けない ・Bellman-Fordの無駄な計算を省略した改良バージョンと解釈できる	・負の辺が含まれている場合は解けない ・EはV^2個に比べて小さい場合が多いため、matrixバージョンの無駄を省略し高速に計算できる	・負の辺が含まれていても解ける ・実装が簡単なので計算量に余裕があれば、単一始点問題でもWarshall-Floydを利用するとよい

ダイクストラくらいしか知らなかったが、今回いろいろなアルゴリズムを知ることができて良かった。

使い分けのポイントを簡単にまとめると、

全頂点間の最小距離が必要なときは、Warshall-Floyd。

単一始点で負の辺がある場合は、Bellman-Ford。（※時間に余裕があればWarshall-FloydでもOK。）

単一始点で、負の辺がなく、計算時間の制限が厳しい場合はDijkstra。

この本はかなりお勧め。アルゴリズマーは是非買うべし！！コンピュータアルゴリズムのバイブルになると言っても過言ではないでしょう。