最短経路

最短経路問題とは

最短経路問題(Shortest Pth Problem)とは、重み付きグラフ \(G=(V,E)\) において、ある与えられた頂点の組 \(s,d\) を接続する経路の中で、辺の重みの総和が最小であるパスを求める問題である。この問題は、主に以下の \(2\) つに分類される。

単一始点最短経路

グラフ \(G\) において、与えられた \(1\) つのの頂点 \(s\) から、他の全ての頂点 \(d_i\) への最短経路を求める問題。
アルゴリズムでは、ベルマンフォード法、ダイクストラ法が有名。

全点対間最短経路

グラフ \(G\) において、全ての頂点のペア間の最短経路を求める問題。
アルゴリズムでは、ワーシャル・フロイド法が有名。

ベルマンフォード法

グラフの始点 \(s\) から頂点 \(i\) への最短距離を \(d[i]\) とすると、次の等式が成り立つ。

\(d[i]=min\{d[j]+(j \hspace{4px} から \hspace{4px} i \hspace{4px} への辺のコスト) \hspace{4px} | \hspace{4px} e=(j,i) \in E \}\)

もしグラフがDAGであれば、頂点を順序付けることができるので、この漸化式を用いて \(d\) を計算することができる。しかし、グラフに閉路が含まれる場合は順に計算してくことができない。その場合でも、頂点 \(i\) へ更新していくことで \(d\) を計算することができる。負の閉路が存在しなければ、この更新はいつかは停止し、そのときの \(d\) は最短距離となる。

ダイクストラ法

ダイクストラ法の考え方は以下の動画がわかりやすい。

ダイクストラのアルゴリズム

1.始点に \(0\) を書き込む。
2.未確定の頂点の中から最も小さい値を持つ頂点を \(1\) つ選び、その値を確定させる。
3.上記2.で確定した頂点から直接つながっていて、かつ、未確定な頂点に対してかかるコストを計算し、書き込まれている数より小さい場合は値を書き換える。
4.全ての頂点が確定していない場合は、2に戻る。全ての頂点が確定したら終わり。

ダイクストラのアルゴリズムを実装する

負の辺がない場合、ベルマンフォード法で \(d[i]\) が最短距離でない場合、 \(d[j]=d[i]+(i \hspace{4px} から \hspace{4px} j \hspace{4px} の辺のコスト)\) と更新できたとしても、 \(d[j]\) は最終的な最短距離にはならない。また、 \(d[i]\) が変化していない場合でも、頂点 \(i\) から出ている辺を毎回見ている。これらは無駄なので、以下の修正を行う。

1.最短距離が確定した頂点と隣接している頂点を更新する。
2.1で使った「最短距離が確定した頂点」はもう使わない。

1と2のうち、最短距離が確定した頂点をどのように見つけるかが問題になる。初期状態では始点のみ最短距離が確定している。まだ使われていない頂点のうち、距離が \(d[i]\) が最小の頂点は最短距離が確定している。これは、負の辺がないので \(d[i]\) があとでより小さくなることがない。

ワーシャルフロイド法

\(O(|V|^3)\) で全点対間最短路で求めることができる。単純な \(3\) 重ループなので計算量に余裕があれば単一始点最短路問題でも使うことができる。

【出典】
渡部有隆, Ozy, 秋葉拓哉他「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」 295,302〜314,336〜341頁
秋葉拓哉 , 岩田陽一他「プログラミングコンテストチャレンジブック [第2版] ~問題解決のアルゴリズム活用力とコーディングテクニックを鍛える~」 94〜98頁