ダイクストラ法

ダイクストラ法（だいくすとらほう、Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。辺の重みに負数を含む場合はベルマン-フォード法などが使える。辺の重みが全て同一の非負数の場合は幅優先探索が速く、線形時間で最短路を計算可能である。また、無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズムによって線形時間での計算が可能であるが、実用性はあまり高くない。