ダイクストラ法は、始点から各頂点への最短距離を求めます。未確定の中から暫定距離が最小のノードを確定し、そのノードを通る経路で隣接ノードの距離を改善します。

ノードの確定と距離の緩和を示す重み付きグラフのシミュレーター

1. 始点をクリック（現在： A)

2. 1段階ずつ進む

未確定今回確定確定済み今回調べた辺最短経路木選択ノードへの経路

表の黄色いセルは今回更新された距離です。実行後にノードをクリックすると、始点からの最短経路が強調されます。

なぜ最も近いノードを先に確定するのか

未確定の中で最小の暫定距離を持つノードをuとします。他の未確定ノードを通る経路は、その時点ですでにuの距離以上です。辺の重みが非負なら、延長しても短くなりません。負の辺がある場合はこの議論が成り立たないため、ベルマン–フォード法などを使います。

実行時間

ヒープによる優先度付きキューを使うと計算量はO((V + E) log V)です。経路探索やOSPFなどのルーティングにも利用されます。