概要
概要
重みが非負のグラフで単一始点最短経路を求めます。いま最も距離が短い候補を優先度付きキューで選びます。
グラフ / Dijkstra（ダイクストラ法）
重みが非負のグラフで単一始点最短経路を求めます。いま最も距離が短い候補を優先度付きキューで選びます。
目次
このページでわかること
概要
重みが非負のグラフで単一始点最短経路を求めます。いま最も距離が短い候補を優先度付きキューで選びます。
考え方
dist[start] = 0
while pq not empty
take node with min dist
relax outgoing edges要点
O((V+E) log V)
非負重み
Priority Queue
最短経路
補足
一番近い未確定頂点から順に確定することです。
辺の重みを考慮します。
負辺がある場合は Bellman-Ford などを使います。
動きで確認
ここでは「どの頂点が注目か」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。