【最短経路検索】ダイクストラ法を理解してExcelに実装してみた。
最短経路検索の代表的な解法はダイクストラ法
モノをA地点からB地点に運ぶのに、
- 最短距離で運べる経路
- 最短時間で運べる経路
- 最小コストで運べる経路
を知りたい時、Google地図ルート検索やYahoo!路線情報やカーナビ等いろいろな方法がありますが、すべて下記のような単純な問題に帰着します。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
１から６に移動するのに、最もコストが安くなるルートはどれでしょうか？
但し、黒字は各ノード間を移動するコストとします。
＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊
この問題では、１⇒４⇒３⇒６と移動するとコストが１２となり一番安くなりますが、黒字の数字を距離とすれば最短距離を求める問題になり、時間とすれば最短時間を求める問題になります。
つまり、この３つの問題は本質的に同じことです。
この問題は線形計画法でも解くことができます。
【最短経路検索】Excelのソルバー機能を使って線形計画法で解いてみた
でも、もっと簡単な方法があります。
中でも有名なアルゴリズムがダイクストラ法です。
このアルゴリズムは驚くほど単純ですが、Google地図ルート検索やYahoo!路線情報やカーナビでも使われている有名な方法です。
今回はこのアルゴリズムの考え方を理解した後、Excelに実装して試してみたいと思います。
ダイクストラ法のアルゴリズム
負のコストがないとすると、ノードを進むに従って累積コストは増加します。
また、そのノードに到達するルートによって、累積コストは異なります。
すべてのルートについて虱潰しに累積コストを調べれば最小値を求められますが、それではノードが多くなると計算に時間がかかり過ぎます。
そこで、ダイクストラ法では
「他のルートから到達しても、絶対に累積コストがそれ以上大きくならないノード」
については累積コスト確定してしまい、それ以降は調べません。
具体的には、次のようなアルゴリズムになります。
- 始点ノードの累積コストをゼロ、その他を無限大とする。
- 確定していないノードの中で累積コストが最小のノードを確定させる。
- 確定したノードに隣接するノードの累積コストを計算する。この時、
- 確定しているノードの累積コストは計算しない。
- 未確定のノードについては、元からある累積コストより小さくなる場合だけ更新する。
- ２に戻る。
これをすべてのノードが確定するまで続けるだけです。
冒頭の例でやってみると、以下のようになります。
まず始点ノードの累積コストをゼロ、その他のノードの累積コストを無限大として、各ノードに書き入れます。
ここでは分かり易いように無限大ではなく、９９を書き入れました。
次に、確定していないノードの中で累積コストが最小のノードを確定します。
確定したノードは赤色で塗りつぶすことにします。
次に、確定したノードに隣接するノードの累積コストを計算して、元の累積コストより小さい場合は書き換えます。
この場合、隣接する３つのノードの累積コストはすべて９９ですので、すべて書き換えます。
次に、未確定のノードの中で累積コストが最小のものを確定させます。（ここでステップ２に戻っています）
続いて、確定したノードに隣接したノードの累積コストを計算します。
中央のノードへ行く場合の累積コストは２＋９＝１１になりますが、元の累積コストが４で１３よりも大きいので、４のままにします。
続いて、未確定のノードの中で累積コストが最小のノードを確定させます。
以下、同様に繰り返します。
これですべて確定しました。
最小コストは１２で、その時の経路は下記の通りです。
ダイクストラ法をExcelに実装する
このようにダイクストラ法のアルゴリズム自体は単純で、ノードを結ぶデータ（コスト、距離、時間等）さえ揃えれば、簡単に解けることが分かっていただけたと思います。
ただ実際の道路網や鉄道網で使おうとするとノード数が膨大なので、コンピュータの力を借りないと計算に何年もかかってしまいます。
ここではプログラミング言語なんて知らないというあなたでも解ける方法を紹介します。
それはExcelを使うことです。
VBAも使わずに、Excel関数だけで最短経路問題を解くことができます。
まず、ネットワークの情報を下表のようにまとめます。
（ノードの数字はノード番号）
この表は隣接するノード間のコストをまとめたものです。
例えばノード４から１０へ行くコストは１０ですので、４行６列には１０が入力されています。
次にこのコスト表はあくまでも隣接ノード間のコストですので、累積コスト表も作っておきます。
確定したノードの累積コストをA列に入力することにより、そのノードから隣接するノードの累積コストが計算されるようにしておきます。
次に、累積コストを見ながらノードを順次確定させていくロジックを組みます。
これは、確定させるノードごとに別の表を用意します。
最初のノード１は累積コストゼロで確定ですので、次のノードを確定させるところから行います。
ノード１を確定させると隣接するノードは２、４、５なので、それぞれのコストを関数で書き入れます。
すると、この中で最小値は０を除くと２で、そのノードは２です。
これを関数で計算させて、ノード２を次回の確定ノードして使います。
次にノード２に隣接するノードの累積コストを求め、未確定のノードの中で最小の累積コストを求めます。
そのために、確定した累積コストも消さないでおいて、それらを除外した中での最小値を求めます。
具体的には下記のようにします。
これで新たにノード４が確定したので、次のステップ３でこのノードを前回確定ノードとして同じように計算します。
以下同様に繰り返すと、ステップ５で終了します。
これにより、各ノードの累積コストがすべて確定し、最終ノードの累積コストは１２が最小値となります。
また、その時のルートは最終ノードの６から遡っていくことにより、６⇐３⇐４⇐１となります。
これもExcel関数を使えば、次のように自動化できます。
