ダイクストラ法による単一始点最短経路を求めるアルゴリズム

2020年3月7日グラフグラフ, 競プロ, 重み付きグラフ, 単一始点最短経路, 最短経路, ダイクストラ法, ヒープ, 優先度付きキュー, 貪欲法

グラフにおける単一始点最短経路問題とは、始点を固定した時に、他のすべての頂点への最短経路を求める問題のことです。

ダイクストラ法は、単一始点最短経路問題を解く時に利用され、利点としては

  • 計算量が \(O(|E| \log |V|)\) であり、ベルマンフォード法の計算量 \(O(|E|×|V|)\) よりも高速に動作する

というのが挙げられます。一方で、欠点として

  • 負の辺があるときに使用できない

というのがありますが、最短経路を求める非常に有名なアルゴリズムの一つです。

アルゴリズム

ダイクストラ法:

  1. 始点 s を「既に最短距離が確定した頂点」、他の頂点を「まだ最短距離が確定していない頂点」とする
  2. 以下をすべての頂点の最短距離が確定するまで繰り返す
    1. 全ての「既に最短距離が確定した頂点 u 」から「まだ最短距離が確定していない頂点 v 」へ伸びる全ての辺 e=(u,v) について、「v と d[v] の候補」をまとめておく
    2. 候補の中から、d[v] が最小のものを選択し、v を「既に最短距離が確定した頂点」に加える

※ 頂点集合を V・辺の集合を E とした、グラフ G=(V,E) において、始点 s から 頂点 v への最短距離を d[v] としています。

※ ダイクストラ法は、行ける場所の中から「最も早く行ける場所」を順番に確定させていきます。

頂点 1, 2, 3 の中から最短で行ける場所を探す
頂点 2 へ最短で行けるため確定

計算量

  • ヒープを使わない場合:
    • \(O(|V|^2)\)
  • ヒープを使う時:
    • \(O(|E| \log |V|)\)

候補の中から d[v] が最小のものを選択するには、単純にやると全ての候補を確認することになるので \(O(|V|)\) の計算量がかかってしまいます。これを頂点数だけ繰り返すので、この場合の計算量は \(O(|V|^2)\) です。

しかし、ヒープなどのデータ構造を上手く使うと候補の追加や最小値の取得が \(O(\log |V|)\) で計算できます。この時の、更新と取り出しの回数は辺の数だけ生じるので \(O(|E|)\) です。

\(|E|\) が小さければ、後者の方が高速に動きます。

C++での実装例

ヒープを利用した時の実装例です。

C++ では STL の priority_queue をヒープとして利用することができます。

以下の実装では、仮の「頂点と最短距離」を全て priority_queue に入れているので、\(O(|E| \log |E|)\) の計算量になりそうですが、最短距離でない場合は無視をすることで、\(O(|E| \log |V|)\) になっています。(いずれにせよ \(\log |E| \leq \log |V|^2 = 2 \log |V|\) から同じ計算量になります。)

最短距離の経路復元

ダイクストラ法で最短距離を求めるついでに、「1つ前にどの頂点を通ったか」を記録しておけば、終点から逆にたどっていくことで、最短距離の経路を復元することができます。

先程の関数を少し拡張すると以下のようになります。prev という vector に「1つ前にどの頂点を通ったか」記録しています。

記録した点を用いて、後ろから始点 r へとたどっていくことで経路を復元することができます。

アルゴリズムの考え方と正当性

基本となる式と考え方

頂点集合を V・辺の集合を E とした、グラフ G=(V,E) において、始点 s から 頂点 t への最短距離を d[t] と表すことにします。

基本はベルマンフォード法と同じく以下の式が成立することを利用します。

  • d[v] = min{ d[u] + ( 辺e=(u,v) の距離 ) }

この式を利用して、最短距離を始点 s に近い頂点から順番に決定していくことができれば、すべての頂点に対して最短距離を求めることが可能です。

最短距離を1つずつ確定させていく

ベルマンフォード法での問題点は何かというと、「ある頂点までの最短距離が求まったかどうか最後まで分からない」というところにありました。

しかし、「負の辺が存在しない」という仮定を入れると、「最短距離が求まった頂点」を順番に決定していくことができます。

ダイクストラ法では、最短距離を以下のように確定させていきます。

  1. 「最短距離が確定した点集合」とつながる頂点について、最短距離 d[i] の候補をまとめておく
  2. 候補の中から、最もd[i] が小さい頂点を「最短経路が確定した点集合」に加える

具体例で確認

先程の手順を具体例で確認してみましょう。

「最短距離が求まった頂点」を水色・「まだ最短距離が確定していない点」のうち水色のものと繋がっているものを灰色で表すことにします。

始点のみが最短距離が確定

灰色のノードが、次に更新されるノードの候補です。

  • s→2:d[2] = 1
  • s→3:d[3] = 3
  • s→1:d[1] = 5

という候補があるので、この中から距離が最小のものを選びます。

s と 2 の間の辺のコストが最小

これで、s と 2 が「最短距離が確定した頂点」になりました。次の候補としては、

  • s→2→1:d[1] = 1+2 = 3
  • (s→1:d[1] = 5)
  • s→3:d[3]= 3

があり、この中から距離が最小のものを選択します。(d[1]に関してはより距離が小さい方を残します。)

あとの候補の残りは以下1つだけです。

  • s→3:d[3]= 3

3が確定した頂点になったので、4を灰色に変更しました。

あとの候補の残りは以下の通りです。

  • s→3→4:d[4] = 3+1 = 4

これで終了です。これ以上頂点が更新されることはありません。

以上で見たように、「最短距離が小さいもの」から順番に頂点を確定させていくことができます。これは、「負の辺が存在しない」という仮定があったからできることです。

練習問題