研究成果 > アルゴリズムのデモ > 最短路問題

最短路問題とは

この問題は，出発地点から目的地点までの経路のうち道のりが最小になるもの（最短路）を見つける問題です． 実は，以下に説明するアルゴリズムの仕組みにより，出発地点さえ決まれば，そこから他の地点を目的地点とし た最短路が求まりますので目的地点は特に指定しないことにします．

アルゴリズム

アルゴリズムの進行は次のようになります．まず，出発地点に最も近い地点が見つかり，次に出発地点に 2番目 に近い地点が見つかり，順に，出発地点に近い地点が求まっていきます．i番目に近い地点は次のルールに従っ て選ばれます．

ルール D： 「残りの地点の中で， すでに選ばれた地点（1番目〜 i-1番目に近い地点）のみを経由して出発地点に最も近い地点を選ぶ」
このルール D に従えば，出発地点から他の地点への最短経路が順に見つかることが保障されています． このアルゴリズムは提案者 Dijkstra に因んでダイクストラ法と呼ばれています． この様子をデモでご覧ください．

デモの説明

デモ Dijkstra1 を選択してクリックすると48地点の問題例が 呼び出されます（Dijkstra2, Dijkstra3, Dijkstra4 はそれぞれ地点 数が 105, 225, 532 の問題例です）．呼び出された画面には各地点が緑の点で描かれています．デモの問題例 では，2地点間に枝（青色線分）があるときその 2地点間で行き来ができ，その移動距離は線分の長さとします． 出発地点はオレンジ色で表示されています．[青い線分が生成される過程が終わるまで少しお待ちください]

遊び方

オレンジ色の点が出発地点です．計算開始前にカーソル移動をさせると 好きな緑の地点を出発地点（オレンジ色）に選ぶことができます．

アルゴリズムは与えられた出発地点から先に述べたルール D で出発地点に「次に近い地点」を選びます．その 際，「先に選ばれている地点」からいま選んだ地点へ向かう枝が 1本だけオレンジ色に着色されます．この枝は， 今選ばれた地点への最短経路の最後の枝であることを意味しています．この計算を続けることにより，オレンジ 色の枝は常に，出発地点からその周辺に樹状に伸びていくことが分かります．計算が終了した後に得られたオレ ンジの樹を使えば，出発地点から他のどの地点への最短経路も直ちに分かります．オレンジの樹に沿った出発地 点から目的の地点までの経路（これは唯一）を選ぶだけです．