ダイクストラ法 - hkurokawa-cp

ダイクストラ法

グラフ$ G = (V, E)における始点$ sから各頂点への最短経路を求めるアルゴリズム。疑似コードは以下のようになる。

code:pseudo

// 初期化

各頂点 v について d(v) = INF ただし d(s) = 0

優先度付きキュー Q に (s, 0) を入れる

while Qが空でない

(u, c) ← Qからcが最小の頂点を取り出す

for each u からの辺がある頂点 v

new_dist = d(u) + cost(u, v)

if new_dist < d(v)

d(v) = new_dist

Q に (v, new_dist) を入れる

Java版は以下。

code:Dijkstra.java

long[] dist = new longV;

for (int i = 0; i < V; i++) disti = INF;

dists = 0;

PriorityQueue<Node> toVisit = new PriorityQueue<>(Comparator.comparingLong(o -> o.dist));

toVisit.add(new Node(s, 0));

while (!toVisit.isEmpty()) {

Node n = toVisit.remove();

if (distn.number < n.dist) continue; // 1) すでに訪問済みの頂点は無視する

for(Edge e : graphn.number) {

int i = e.to;

int cost = e.cost;

long newValue = diste.from + cost;

if (disti > newValue) {

disti = newValue;　// 2) この時点で距離を更新する。ここで更新された値の最小値のみが 1)を通過できる。

toVisit.add(new Node(i, newValue)); // 同じノードiの値は複数入ることに注意。最小値以外は1)で無視される。

}

return dist;