ダイクストラ法
正式名称
Dijkstra's Algorithm
一言でいうと
非負の重みを持つグラフで最短経路を求めるアルゴリズム
初心者向け説明
始点から各頂点までの暫定距離を更新しながら、最も近い頂点を順に確定して最短経路を求めます。
ポイント
- 辺の重みが負の場合にはそのまま適用できない
- 単一始点最短経路問題に使う
- 優先度付きキューと組み合わせる実装も多い
関連用語
関連記事
- 探索アルゴリズムとは？線形探索・二分探索・ハッシュ探索・DFS・BFSを基礎から理解しよう
🍯 はちみつメモ
ダイクストラ法 = 非負の重みを持つグラフで最短経路を求めるアルゴリズム