ダイクストラ法

ダイクストラ法とは

ダイクストラ法は、グラフ理論における最短経路問題を解決するための代表的なアルゴリズムです。

点と点を結ぶ辺に距離（重み）が設定されたグラフが与えられたとき、スタートの点からゴールの点への最短経路を求めるアルゴリズムです。 非負の重みを持つグラフに対して適用可能であり、効率的に最短経路を見つけることができます。（辺の重みが負だとそこを通れば無限に経路長をマイナスにできるため）

理屈としては、最短経路の一部は最短経路である、という性質を利用しています。つまり、ある点までの最短経路が分かれば、その点からさらに他の点への最短経路も効率的に求められる、ということです。各点への最短経路を順々に見つけ、ゴールに到達するまで探索を続けます。

ちなみにダイクストラ法を視覚的に理解するページを作ったので、興味があればぜひ見てみてください。

ダイクストラ法の実装例

点の数をN、辺の数をMとします。点は1からNまでの番号が振られているとします。そして始点を1、終点をNとします。 各辺は「始点、終点、重み」の3つの情報で表されます。今回は辺は双方向であるとします。

まとめ

ここではダイクストラ法の基本的な考え方とTypeScriptでの実装例を紹介しました。ダイクストラ法は最短経路問題を解決するための強力なアルゴリズムであり、非常に有名なアルゴリズムの１つです。

プログラミング問題集などでも頻出のアルゴリズムなので、ぜひ理解を深めて実装できるようにしておきましょう。