競技プログラミングで頻出のダイクストラ法について実装してみました。
例題も解いて解説していきます。
ダイクストラ法とは
経路の最短距離を求めるアルゴリズムです。
wikipediaより引用
ダイクストラ法（だいくすとらほう、英: Dijkstra's algorithm）はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムである。辺の重みに負数を含む場合はベルマン-フォード法などが使える。辺の重みが全て同一の非負数の場合は幅優先探索が速く、線形時間で最短路を計算可能である。また、無向グラフで辺の重みが正整数の場合は、Thorupのアルゴリズム[1]によって線形時間での計算が可能であるが、実用性はあまり高くない[要出典]。
- 辺の重みがない（単一の）場合はBFSが早い
- 辺の重みに負数を含む場合はベルマン-フォード法
が使えるようです。
今回は辺の重みがすべて非負整数であるグラフについてのダイクストラ法を実装していきます。
求め方
ダイクストラでの最短経路の求め方は以下のとおりです。
- 始点に0を設定する。（未確定。その他のノードには便宜的に
INFなどを入れておくことが多い） - 未確定のノードから、最短のものを一つ選択し、そこを確定させる。
- 2.で確定したノードから直接つながっているノードに対して、かかる時間を計算する。そのノードが現状持っている最短経路より短ければ、その値で更新する。
- すべてのノードが確定していれば、終了。確定していなければ、2に戻る。
図解してみます。以下のような図を考えてみましょう。
Sと書いてあるところを始点として、各地点（ノード）の最短経路を求めていきましょう。
順番にアルゴリズムを追っていきます。
- 始点に0を設定する。（未確定。その他のノードには便宜的に
INFなどを入れておくことが多い）
- 未確定のノードから、最短のものを一つ選択し、そこを確定させる。
→１と書いてあるノードが未確定かつ最短なのでそこを確定させます。
- 2.で確定したノードから直接つながっているノードに対して、かかる時間を計算する。そのノードが現状持っている最短経路より短ければ、その値で更新する。
→１と書いてあるノードと隣り合っている３つのノードに対して、１からの距離を求めて、その値で更新します。
上から0+5, 0+3, 0+4を計算します。一応矢印も書いておきましょう。
-
すべてのノードが確定していれば、終了。確定していなければ、2に戻る。
→2に戻ります。 -
未確定のノードから、最短のものを一つ選択し、そこを確定させる。
→3と書いてあるところが最短です。
- 2.で確定したノードから直接つながっているノードに対して、かかる時間を計算する。そのノードが現状持っている最短経路より短ければ、その値で更新する。
→３と書かれたノードから見て、隣り合う未確定のノードについて、距離を計算し、現在書かれている数字より小さければ更新します。
- すべてのノードが確定していれば、終了。確定していなければ、2に戻る。
- 未確定のノードから、最短のものを一つ選択し、そこを確定させる。
→まず上段の４と書いてあるノードを確定させましょう。
-
2.で確定したノードから直接つながっているノードに対して、かかる時間を計算する。そのノードが現状持っている最短経路より短ければ、その値で更新する。
→特に変更なし。 -
すべてのノードが確定していれば、終了。確定していなければ、2に戻る。
-
未確定のノードから、最短のものを一つ選択し、そこを確定させる。
-
2.で確定したノードから直接つながっているノードに対して、かかる時間を計算する。そのノードが現状持っている最短経路より短ければ、その値で更新する。
→特に変更なし。 -
すべてのノードが確定していれば、終了。確定していなければ、2に戻る。
-
未確定のノードから、最短のものを一つ選択し、そこを確定させる。
-
2.で確定したノードから直接つながっているノードに対して、かかる時間を計算する。そのノードが現状持っている最短経路より短ければ、その値で更新する。
→特に変更なし。 -
すべてのノードが確定していれば、終了。確定していなければ、2に戻る。
-
未確定のノードから、最短のものを一つ選択し、そこを確定させる。
-
2.で確定したノードから直接つながっているノードに対して、かかる時間を計算する。そのノードが現状持っている最短経路より短ければ、その値で更新する。
→特に変更なし。 -
すべてのノードが確定していれば、終了。確定していなければ、2に戻る。
→すべてのノードが確定したので、終了です。
はい。左端のノードからそれぞれのノードまでの最短距離、並びに経路もついでに求めることが出来ました。
どんどんノードが確定していくのがわかりやすいですね。
では、コードに落としていきましょう。
実装
問題を解きながら実装していきます。
解く問題はAOJ Single Source Shortest Path Iです。
頂点数が最大100なので、なにも考えずダイクストラを実装していきます。
ACコードは以下です。
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<ArrayList<Integer>> edge = new ArrayList<>(); // 頂点と接続している点
for (int i = 0; i < n; i++) {
edge.add(new ArrayList<>()); // 初期化
}
long[][] cost = new long[n][n]; // 2点間の距離
boolean[] used = new boolean[n]; // 確定したかどうか
long ans[] = new long[n]; // 頂点0からの最短距離
// 入力の受け取り
for (int i = 0; i < n; i++) {
int u = sc.nextInt(); // 頂点
int k = sc.nextInt(); // 頂点uからの出自数
for (int j = 0; j < k; j++) {
int v = sc.nextInt(); // uと隣接する頂点
long c = sc.nextInt(); // uとvの距離（重み）
edge.get(u).add(v); // uとvが隣接しているという情報を格納
cost[u][v] = c; // uからvへの距離（重み）を更新
}
}
// ここからダイクストラ
/*
* 始点に0を設定する。（未確定。その他のノードには便宜的にINFなどを入れておくことが多い）
*/
for (int i = 0; i < n; i++) {
ans[i] = Long.MAX_VALUE;
}
ans[0] = 0;
for (;;) {
/*
* 未確定のノードから、最短のものを一つ選択し、そこを確定させる。
*/
long minDistance = Long.MAX_VALUE;
int minTyoten = -1;
for (int i = 0; i < n; i++) {
if (!used[i]) {
if (minDistance > ans[i]) {
minDistance = ans[i];
minTyoten = i;
}
}
}
/*
* すべてのノードが確定していれば、終了。確定していなければ、最初に戻る
*/
if (minDistance == Long.MAX_VALUE) {
break;
}
// 頂点を確定させる。
used[minTyoten] = true;
/*
* 直前で確定したノードから直接つながっているノードに対して、かかる時間を計算する。
* そのノードが現状持っている最短経路より短ければ、その値で更新する。
*/
for (int next : edge.get(minTyoten)) {
if (ans[next] > ans[minTyoten] + cost[minTyoten][next]) {
ans[next] = ans[minTyoten] + cost[minTyoten][next];
}
}
}
// 答えの出力
int i = 0;
for (long h : ans) {
System.out.println(i++ + " " + h);
}
}
}
図で解説したとおりに実装してみました。
計算量的にはO(n^2)となりそうです。
今回は愚直に実装しましたが、ダイクストラ法のなかの「すべてのノードの中から最小のノードを見つける処理」に関しては「優先度付きキュー」を使用すると計算量が減るようです。
これについてはパッと見でちょっと複雑そうだったのでまたの機会に勉強しようと思います。
今回はとりあえず愚直にダイクストラを実装してみたという感じです。