ダイクストラ法ってなに？
皆さん、こんにちは！
ハリーです。競プロ精進日記の４週目になります。今回は、新しいアルゴリズムを学んでいきたいと思います。今回、勉強していくアルゴリズムは「ダイクストラ法」です。
それではやっていきましょう！
ダイクストラ法
ダイクストラ法とは、グラフ上の2頂点間の最短経路を求めるアルゴリズムで、1959年にEdsger Dijkstra氏 によって考案されました。
例題を見ながら考えていきましょう。
◆例題
ハリーくんの家とＲくんの家があります。ハリーくんは R くんの家に行きたいと思っています。R くんの家に行く道の途中には、いくつか交差点があります。ハリーくんは歩くのがとても嫌いなので、最短の経路で R くんの家に行こうと考えています。歩く速度は一定です。最短で何分で R くんの家に着くことができるでしょうか。
例えば、下記の経路で R くんの家に行くと 14 分で着くことができます。
しかし、最短経路で R くんの家に行くと 9 分で着くことができます。
グラフ理論において、ここで示された交差点(頂点) のことを「ノード」、道(辺) のことを「エッジ」、各道の所要時間を「重み」と呼ばれています。
上記の例題は、「単一始点最短経路問題」という最短経路を求める問題のひとつです。今回の例題は、頂点の数も少なくシンプルな問題でしたが、今回の例題よりも、ノードやエッジの数が増えていくと経路のパターンはもっと増加します。
ダイクストラ法の手順
- スタート点からスタート点までの確定距離を0とする。
- 距離が確定した点と隣り合っている点までの暫定距離とたどる元の点を求める。
（暫定距離 ＝ 確定距離 ＋ 隣り合っている点までの移動距離）
ただし、隣り合っている点の暫定距離がすでに求まっている場合、より短い暫定距離が出た場合のみ上書きする。また、隣り合っている点の確定距離がすでに求まっている場合は無視する（すでに確定してるので更新されない）。 - 暫定距離が出ている点の中で、一番暫定距離が小さいものを確定距離とする。
- すべての距離が確定するまで2, 3を繰り返す。距離が確定した際の経路は、ゴールから元の点をたどっていることで求めることができる。
先ほどの例題でもう一度考えてみましょう。
各ノードに a ～ e の名前をつけます。そして、V（頂点全体集合）と S（頂点集合）、V-S（Sに含まれていない頂点集合）をまとめると下図のようになります。
水色で塗られている点は必要な時間が確定している点です。点の外にある赤字の数字は必要な時間を表しています。
次は、a から行くことができる b、c、d について距離の更新を行います。
b、c、d については、8分、5分、3分で移動できるので各ノードに 8、5、3 の数字が入っています。
上図において、まだ色が塗られていない頂点のうち、最も所要時間が短いものを見ます。今回は d が一番短いので d の経路を考えます。
ここで、d が最も総所要時間が短いことを意識して d に行く経路を考えてみると、他の経路を通った場合の総所要時間は必ず 3 以上になってしまうことがわかります。なので、d を塗りつぶします。そして、d から行ける頂点は e しかないので e を塗りつぶします。最後に、e から f に行くことができるので R くんの家に 14 分で行ける経路があることがわかります。
ここからは、先ほどと同じように所要時間が最も短いものを探します。今回は、 c ですね。
b には既に、a → b の経路があり、総所要時間に 8 が入っていましたが、c を経由すると 7 分で移動できることがわかったため更新します。そして、f にも移動できる道があります。この経路は d → e を経由する時間より短い時間で e に行くことができるので、e の総所要時間を更新します。
この後も、同じことを繰り返します。残りの点は b と f ですが、所要時間が短いのは bなので、b を見ていきます。
b を塗りつぶし、総所要時間を更新するために頂点を見ます。こちらは c → f を経由するより短い時間で行くことができるので、総所要時間を更新します。
これで、a から f までの最短経路を求めることができました。
