ダイクストラ法【Dijkstra's algorithm】

概要

ダイクストラ法（Dijkstra's algorithm）とは、様々な経路が考えられる二地点間の最短距離を求めるアルゴリズムの一つ。地点間を繋ぐ辺に距離に相当する重みがある場合を対象に、効率的に最短経路を求めることができる。

始点と終点の間に様々な経由地点（ノード）が散らばっており、ノード間が様々な重みの辺（エッジ）で繋がっているときに、どの経路が最短となるかを求める手順を定めている。エッジの重みは0以上である必要があり、負数を含む場合は他のアルゴリズムが必要となる。

ダイクストラ法では各ノードに始点からの距離（到達経路に含まれる辺の重みの合計）を書き込み、処理の進行に伴って書き換えていく。始点の距離は0であり、終点を含めた始点以外のノードの距離はとりあえず「∞」（無限大）を書き込んで初期化しておく。

「その時点で距離が最小のノードの距離は確定し、そのノードを起点に隣接する（かつ未確定の）ノードの距離を算出し、既存の値より小さければ書き換える」という手順を繰り返す。初回で確定するのは始点の「0」で、始点の隣接ノードに辺の重みを書き込んでいく。

始点の隣接ノードの中で最小の距離のノードはそこで確定となり、次はそのノードに隣接し距離が未確定のノードに距離を書き入れていく。まだ一度も書き込んでいないノードは距離が∞なので隣接ノードからの距離に更新され、他の経路の値が存在するノードは新しい値がより小さければ更新する。

この手順を繰り返していくと、毎回その時点で最も距離が小さいノードが一つずつ確定していく。最終的には終点の値のみが未確定の状態となり、その時点で終点に書き込まれている値が始点から終点までの最短距離となる。各ノードについて最短距離の場合の一つ手前のノードを記録しておくことで、最短経路も知ることができる。

1959年にオランダのコンピュータ科学者エドガー・ダイクストラ（Edsger W. Dijkstra）によって考案されたアルゴリズムで、グラフ理論の基本的なアルゴリズムとしてよく知られる。ネットワーク上のパケットのルーティング、道路や交通機関の経路検索など実用上も広く応用されている。

(2023.10.9更新)