ダイクストラ法とは？
グラフ上のある地点を始点とする最短経路を求める(単一始点最短経路問題を解く)ためのアルゴリズムです。Dijkstra氏によって考案されたことが名前の由来です。
有名なアルゴリズムのため、名前だけは聞いたことがある、という方もいらっしゃるかもしれません。本記事でイメージを掴んでいただければ幸いです。なお、ここでいう”グラフ”はグラフ理論におけるグラフを指しますが、本記事では具体的な例題を用いて解説を進めるため、グラフ理論の事前知識は無くても問題ありません。
ダイクストラ法の考え方
あなたは人気のラーメン屋に行きたいと思っています。
ラーメン屋は下の模式図に示されるような道と交差点を経由して行けることがわかっています。各道の近くにある数字は交通量や信号などを考慮した所要時間(分)を表します。
あなたは多忙なのでラーメン屋に行くまでにかかる時間を最短にしたいと考えています。最短で何分でラーメン屋にたどり着けるでしょうか？
例えば、下の道を通ることにより、8分でラーメン屋まで行くことができます。
しかし、最も所要時間が短くなるのは以下の経路で、所要時間は7分になります。8分の例と比較すると、単純に通る交差点の数が少なければ良いというわけではないことがわかります。”急がば回れ”とはまさにこのことです。
グラフ理論においては、ここで示された交差点(頂点)のことを”ノード”、道(辺)のことを”エッジ”、各道の所要時間を”重み”と呼びます。冒頭の単一始点最短経路問題とは、重みつきグラフ(模式図のようなノードとエッジによって表される関係)において、ある点を始点としたときの各点について、その重み和が最小となるような経路を求める問題であると言い換えることができます。
今回は非常にシンプルな例ですので頂点の数も少なく、8分と7分で比較したような、経路ごとの総所要時間による比較ができました。しかし、ノードやエッジの数が増えていくにつれて経路のパターンは爆発的に増加してしまいます。
■参考動画：『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！
そこで、ダイクストラ法では以下のような手順によって効率的に最短経路を計算します。後ほど図付きで説明しますので、とっつきにくい場合はなんとなくで流して頂いて構いません。
1. 頂点集合全体をVとし、始点からの最短経路(最短距離)が既に確定した頂点集合をSとする。
2. 現時点で経路が判明している頂点のうち、始点からの距離が最小となる頂点vを新たにSに追加する。
3. まだSに含まれていない頂点集合(V - S)のうちvと接する各頂点について、既に求めた最短距離をもとに始点からの最短距離を更新する。
4. 全ての頂点が確定するまで(V - Sが空になるまで)2と3を繰り返す。
ラーメン屋の例に戻って考えましょう。
各ノードにaからeの名前をつけ、図中のノード内の数字で始点からの距離を表すものとすると、始点がSに追加された時点での状態は図のようになります。
緑色で塗られている点は総所要時間が確定した点を表しており、aの中に0が書かれていることは総所要時間が0分であることを意味します。始点なので当然ですね。まだ経路が存在していない部分の総所要時間は”?”としています。
その後、aに隣接する頂点のうちまだ緑色に塗られていないノード、この場合b、c、dについて距離の更新を行います(手順3)。
b、c、dにはそれぞれ7分、4分、3分で移動できるため、ノード内には7、4、3が入っています。
さて、上図においてまだ色が塗られていないSと接する頂点のうち、最も総所要時間が短いものに注目します。この場合はdになります。
ここで、dが最も総所要時間が短いことを意識してdに行く経路を考えてみると、他の経路を通った場合の総所要時間は必ず3以上になってしまうことがわかります。例えば、a → c → e → dのように遠回りしてdに行くことを考えると、cの時点で3以上になってしまいます。cが3未満であるような場合、そもそもdではなくcが最も総所要時間が短い点として選ばれることになるため、アタリマエとも言えます。ちなみに、重みが負になるようなケースでは上記が成立せず、ダイクストラ法を用いることはできません(重みが負の場合にも利用可能なアルゴリズムにはベルマンフォード法などがあります)。
以上の考察から、dまでの最短経路が3であることが確定しましたので、dを緑色に塗り、Sに加えます(手順2の繰り返し)。そして、dからはeに行くことができるので、ラーメン屋に8分で行ける経路が存在することが判明します(手順3の繰り返し)。
ここから、先ほどと同じように総所要時間が最も短いものを探します。今回はcですね。cからはbとeにアクセスできますので、順に見ていきましょう。
bには既にa → bの経路が存在するため、総所要時間に7が入っていました。しかし、cを経由する新たな経路が4 + 1 = 5の時間でbに移動できることが判明したため、総所要時間が更新されています。一方で、eにもdを経由する経路があったため既に数字が入っていますが、こちらはcを経由する経路の方が時間がかかってしまう(4 + 6 = 10)ため、数字は更新されていません。
この後も同じことを繰り返します。残りの点はbとeですが、総所要時間に注目するとbの方が短時間で到達できます。
bをSに加え(緑色に塗り)、総所要時間を更新するために隣接する頂点をチェックします。すると、bを通る経路(5 + 2)はそれまで最適だったdを通る経路(3 + 5)よりも短いことが判明し、eの総所要時間は7に更新されます。
最後に残っているのはeですが、新たに更新されるべきV - Sが存在しないため、これにて終了です。ダイクストラ法によって総所要時間は7分が最短であることを求められました。
以上がダイクストラ法の考え方になります。
実装上は総所要時間が最も少ない点を効率的に選ぶために優先度付きキューを用いることが多く、「V - Sが空になるまで処理を行う」代わりに、「距離が更新される場合は更新とともにキューに追加しておき、キューが空になるまで処理を行う」ことが多いかと思います。
また、今回は簡単のため総所要時間を求めましたが、この考え方を用いて更新時にどのノードから来たのかを別途保持しておくことにより、最短経路を復元することができます。
アルゴリズムの重要性
いかがでしたでしょうか？プログラミングをする上では、単に言語を習得するだけでなく、「アルゴリズムへの理解度」がますます問われてくるのではないでしょうか？
プログラマーの方はもちろん、プログラミングをしない人もより効率的、効果的な業務のためにアルゴリズム学習を進めてみることをオススメします。
－－－－－参考情報－－－－－
■TV出演動画：ええじゃない課Biz（2022/05/29 放送 TOKYO MX）
アンタッチャブル柴田さん、アルコ＆ピースさんがレギュラーのビジネス情報番組「ええじゃない課Biz」にて、プログラミングスキル判定サービス「TOPSIC」と企業・学校対抗プログラミングコンテスト「PG BATTLE」のご紹介をさせていただきました。5分位の動画ですので、ぜひご覧くださいませ。
