【最短経路検索】ダイクストラ法を理解してExcelに実装してみた。

2024年10月6日

◆仕事や勉強の息抜きに。。。

最短経路検索の代表的な解法はダイクストラ法

モノをA地点からB地点に運ぶのに、

  • 最短距離で運べる経路
  • 最短時間で運べる経路
  • 最小コストで運べる経路

を知りたい時、Google地図ルート検索Yahoo!路線情報カーナビ等いろいろな方法がありますが、すべて下記のような単純な問題に帰着します。

*****************************

1から6に移動するのに、最もコストが安くなるルートはどれでしょうか?

但し、黒字は各ノード間を移動するコストとします。

*****************************

 

この問題では、1⇒4⇒3⇒6と移動するとコストが12となり一番安くなりますが、黒字の数字を距離とすれば最短距離を求める問題になり、時間とすれば最短時間を求める問題になります。

つまり、この3つの問題は本質的に同じことです。

 

この問題は線形計画法でも解くことができます。

【最短経路検索】Excelのソルバー機能を使って線形計画法で解いてみた

 

でも、もっと簡単な方法があります。

中でも有名なアルゴリズムがダイクストラ法です。

このアルゴリズムは驚くほど単純ですが、Google地図ルート検索Yahoo!路線情報カーナビでも使われている有名な方法です。

今回はこのアルゴリズムの考え方を理解した後、Excelに実装して試してみたいと思います。

 

ダイクストラ法のアルゴリズム

負のコストがないとすると、ノードを進むに従って累積コストは増加します。

また、そのノードに到達するルートによって、累積コストは異なります。

すべてのルートについて虱潰しに累積コストを調べれば最小値を求められますが、それではノードが多くなると計算に時間がかかり過ぎます。

そこで、ダイクストラ法では

他のルートから到達しても、絶対に累積コストがそれ以上大きくならないノード

については累積コスト確定してしまい、それ以降は調べません。

 

具体的には、次のようなアルゴリズムになります。

  1. 始点ノードの累積コストをゼロ、その他を無限大とする。
  2. 確定していないノードの中で累積コストが最小のノードを確定させる。
  3. 確定したノードに隣接するノードの累積コストを計算する。この時、
    1. 確定しているノードの累積コストは計算しない
    2. 未確定のノードについては、元からある累積コストより小さくなる場合だけ更新する。
  4. 2に戻る。

これをすべてのノードが確定するまで続けるだけです。

冒頭の例でやってみると、以下のようになります。

まず始点ノードの累積コストをゼロ、その他のノードの累積コストを無限大として、各ノードに書き入れます。

ここでは分かり易いように無限大ではなく、99を書き入れました。

 

次に、確定していないノードの中で累積コストが最小のノードを確定します。

確定したノードは赤色で塗りつぶすことにします。

 

次に、確定したノードに隣接するノードの累積コストを計算して、元の累積コストより小さい場合は書き換えます。

この場合、隣接する3つのノードの累積コストはすべて99ですので、すべて書き換えます。

 

次に、未確定のノードの中で累積コストが最小のものを確定させます。(ここでステップ2に戻っています)

 

続いて、確定したノードに隣接したノードの累積コストを計算します。

中央のノードへ行く場合の累積コストは2+9=11になりますが、元の累積コストが4で13よりも大きいので、4のままにします

 

続いて、未確定のノードの中で累積コストが最小のノードを確定させます。

 

以下、同様に繰り返します。

 

 

 

 

 

 

これですべて確定しました。

最小コストは12で、その時の経路は下記の通りです。

 

ダイクストラ法をExcelに実装する

このようにダイクストラ法のアルゴリズム自体は単純で、ノードを結ぶデータ(コスト、距離、時間等)さえ揃えれば、簡単に解けることが分かっていただけたと思います。

ただ実際の道路網鉄道網で使おうとするとノード数が膨大なので、コンピュータの力を借りないと計算に何年もかかってしまいます。

ここではプログラミング言語なんて知らないというあなたでも解ける方法を紹介します。

それはExcelを使うことです。

VBAも使わずに、Excel関数だけで最短経路問題を解くことができます。

 

まず、ネットワークの情報を下表のようにまとめます。

(ノードの数字はノード番号)

 

 

この表は隣接するノード間のコストをまとめたものです。

例えばノード4から10へ行くコストは10ですので、4行6列には10が入力されています。

 

次にこのコスト表はあくまでも隣接ノード間のコストですので、累積コスト表も作っておきます。

確定したノードの累積コストをA列に入力することにより、そのノードから隣接するノードの累積コストが計算されるようにしておきます。

クリックすると拡大します

 

次に、累積コストを見ながらノードを順次確定させていくロジックを組みます。

これは、確定させるノードごとに別の表を用意します。

最初のノード1は累積コストゼロで確定ですので、次のノードを確定させるところから行います。

ノード1を確定させると隣接するノードは2、4、5なので、それぞれのコストを関数で書き入れます。

クリックすると拡大します

 

すると、この中で最小値は0を除くとで、そのノードはです。

これを関数で計算させて、ノード2を次回の確定ノードして使います。

 

次にノード2に隣接するノードの累積コストを求め、未確定のノードの中で最小の累積コストを求めます。

そのために、確定した累積コストも消さないでおいて、それらを除外した中での最小値を求めます。

具体的には下記のようにします。

クリックすると拡大します

 

これで新たにノード4が確定したので、次のステップ3でこのノードを前回確定ノードとして同じように計算します。

クリックすると拡大します

 

以下同様に繰り返すと、ステップ5で終了します。

クリックすると拡大します

 

これにより、各ノードの累積コストがすべて確定し、最終ノードの累積コストは12が最小値となります。

また、その時のルートは最終ノードの6から遡っていくことにより、⇐3⇐4⇐1となります。

 

これもExcel関数を使えば、次のように自動化できます。