ダイクストラ法とは？グラフの最短経路を求めるアルゴリズムの基本と実行例

定義

ダイクストラ法（Dijkstra's algorithm）は、連結グラフにおいて、起点となるノード（始点ノード）から他のすべてのノードへの最短経路を求めるアルゴリズムです。このアルゴリズムは、始点ノードを根とする「最短経路木（shortest path tree）」を生成します。コンピュータネットワークの分野では、ルーティングコストを最小化するための最適な経路の算出に広く活用されています。

ダイクストラ法の手順

入力 − ネットワークを表すグラフと、始点ノード s
出力 − s を根とする最短経路木 spt[]

初期化

• サイズ |V|（ノード数）の距離配列 dist[] を用意します。dist[s] = 0 とし、s 以外のノード u に対しては dist[u] = ∞（無限大） とします。
• グラフ内のすべてのノードを含む集合 Q を用意します。アルゴリズムが完了すると、Q は空になります。
• 訪問済みノードを格納するための空の集合 S を用意します。アルゴリズム完了時には、S にグラフ内の全ノードが含まれます。
• Q が空になるまで、以下の処理を繰り返します。
  • Q から、dist[u] が最小であり、かつ S に含まれていないノード u を取り出します。最初の実行では dist[s] が選ばれます。
  • u を S に追加し、u を訪問済みとしてマークします。
  • u に隣接する各ノード v について、dist[v] を次のように更新します。
    • もし（dist[u] ＋ 辺 u-v の重み）＜ dist[v] ならば、dist[v] ＝ dist[u] ＋ 辺 u-v の重み に更新します。
• 最終的に、配列 dist[] には始点 s から他のすべてのノードへの最短距離が格納されます。

実行例

アルゴリズムの動作は、具体例を使うと最もよく理解できます。ここでは、A から G までのノードが重み付きの辺で接続された次のグラフを考えます。

初期化後の状態は以下の通りです。

• dist[7] = {0, ∞, ∞, ∞, ∞, ∞, ∞}
• Q = {A, B, C, D, E, F, G}
• S = ∅

パス1 − Q の中で dist[] の値が最小の 0 であるノード A を選び、S に移動します。A の隣接ノードは B と C なので、アルゴリズムに従ってそれぞれの dist[] 値を更新します。データ構造の状態は以下のようになります。

• dist[7] = {0, 5, 6, ∞, ∞, ∞, ∞}
• Q = {B, C, D, E, F, G}
• S = {A}

このパス終了後の距離と最短経路は次のグラフの通りです。緑色のノードは、すでに S に追加されたノードを表します。

パス2 − dist[] の値が最小の 5 であるノード B を選び、S に移動します。B の隣接ノードは C、D、E なので、対応する dist[] 値を更新します。データ構造の状態は以下のようになります。

• dist[7] = {0, 5, 6, 12, 13, ∞, ∞}
• Q = {C, D, E, F, G}
• S = {A, B}

このパス終了後の距離と最短経路は次の通りです。

パス3 − dist[] の値が最小の 6 であるノード C を選び、S に移動します。C の隣接ノードは D と F なので、対応する dist[] 値を更新します。データ構造の状態は以下のようになります。

• dist[7] = {0, 5, 6, 8, 13, 10, ∞}
• Q = {D, E, F, G}
• S = {A, B, C}

このパス終了後の距離と最短経路は次の通りです。

パス4 − dist[] の値が最小の 8 であるノード D を選び、S に移動します。D の隣接ノードは E、F、G なので、対応する dist[] 値を更新します。データ構造の状態は以下のようになります。

• dist[7] = {0, 5, 6, 8, 10, 10, 18}
• Q = {E, F, G}
• S = {A, B, C, D}

このパス終了後の距離と最短経路は次の通りです。

パス5 − ノード E と F はどちらも dist[] の値が 10 で同率最小のため、どちらを選んでも構いません。ここでは E を選んで S に移動します。E の隣接ノードは G なので、G に対応する dist[] 値を更新します。データ構造の状態は以下のようになります。

• dist[7] = {0, 5, 6, 8, 10, 10, 13}
• Q = {F, G}
• S = {A, B, C, D, E}

このパス終了後の距離と最短経路は次の通りです。

パス6 − dist[] の値が最小の 10 であるノード F を選び、S に移動します。F の隣接ノードは G ですが、F 経由で G に到達する距離よりも、現在の dist[G] の値の方が小さいため、値は変わりません。データ構造の状態は以下のようになります。

• dist[7] = {0, 5, 6, 8, 10, 10, 13}
• Q = {G}
• S = {A, B, C, D, E, F}

このパス終了後の距離と最短経路は次の通りです。

パス7 − Q にはノードが1つだけ残っています。これを Q から取り出して S に移動します。dist[] 配列の変更は不要です。これで Q が空になり、S にすべてのノードが含まれたため、アルゴリズムは終了です。最後に、どの最短経路にも使用されていない辺や経路を取り除くと、始点ノード A から他のすべてのノードへの最短経路木は次のようになります。