ダイクストラ法

ダイクストラ法は、負のコストがない回路において、ルートを選択を工夫して最短経路を見つけ出していくことで、ベルマンフォード法より効率的に探索することのできるアルゴリズム. 普通の実装では時間計算量はO(n^2)だが、適当なヒープを用いることで時間計算量はO(E+nlog(n))になる. 負のコストが経路になければダイクストラを使い、負のコストがあればベルマンフォードを使う. ダイクストラ法 1. すべてのノードのコストを∞とする 2. 頂点のリストをキューに持っておく. 3. キューから最もコストの低いノードを取り出して、そこから隣接しているノードを更新する.更新したノードはどのノードから来たかを記録しておく. 4. キューが空っぽになるまで3を繰り返す.

ダイクストラ法で最小のコストとして選択したノードは 他のどのノードも自身のコストより高いため、スタート地点からそのノードまでの最小経路として確定できる.