経緯
競技プログラミング練習用にJavaでダイクストラ法を実装してみました。
変数名を適当に付けたりしているので間違い・気になるところあればご指摘ください。
ダイクストラ法とは？
ざっくり簡単に言うと、経路の最短距離を用いるために利用されるアルゴリズム。
詳しい説明に関してはwikipediaの参照をお願いします。
求め方
例題として、この問題で考えてみる。
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_B&lang=jp
以下の重み付きグラフで最短経路を求めてみる。
・出発地点はノード０。
・変数Dminは出発地点からの最短距離。
・出発地点のDminを０として、他ノードにはINF値を入れておく。
ここからダイクストラ法を用いて、最短距離を見つけていく。
(1回目のループ処理)
- まだ訪れていないノードの中で、Dminが最小になるのはノード０。
- ノード０を訪問済みとして、ノード０と隣接するノード(ノード１、ノード２、ノード３)までかかる距離を計測する。
- 計測した距離がDmin以下、つまり現状の最短距離よりも短ければ、その値で更新する。
4.未訪問ノードがなければ、処理を終了。あれば(1)の処理へ。
(3)について。例えばノード０-１間であれば、(3)の処理は、
Dmin[1] = ∞ > Dmin[0] + Length(Node0,Node1) = 0 + 2 = 2
Dmin[2] = ∞ > Dmin[0] + Length(Node0,Node2) = 0 + 3 = 3
Dmin[3] = …
と表すことができる。
1回目の更新後がこちら。
(2回目のループ処理)
- まだ訪れていないノードの中で、Dminが最小になるのはノード３。
- ノード３を訪問済みとして、ノード３と隣接するノード(ノード１、ノード４)までかかる距離を計測する。
- 計測した距離がDmin以下、つまり現状の最短距離よりも短ければ、その値で更新する。
4.未訪問ノードがなければ、処理を終了。あれば(1)の処理へ。
(3)の処理後、隣接するノードのDminは
Dmin[1] = 2
Dmin[2] = 2
Dmin[4] = 3
ノード１に関しては、元々の最短距離が2であるのに対して、ノード０-３-２経由だと距離が5となるので、更新はしない。
2回目の更新後がこちら。
3回目(更新なし)。
4回目。
5回目。
未訪問のノードがなくなったので、処理を終了。
ノード０から各ノードの最短距離が求められる。これをJavaで書いてみる。
コーディング
上の例題に加えて、出発地点Sも変更できるようにする。
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;
public class Dijkstra {
public static void main(String[] args) {
// ノード数と出発地点
int N,S;
// ここから入力に基づいて初期化処理
Scanner sc = new Scanner(System.in);
N = Integer.valueOf(sc.nextLine());
S = Integer.valueOf(sc.nextLine());
boolean[] used = new boolean[N];
ArrayList<Node> nodeList = new ArrayList<Node>();
for(int i = 0; i < N; i++) {
String line = sc.nextLine();
String[] arr = line.split(" ");
HashMap<Integer,Integer> edges = new HashMap<Integer,Integer>();
int num = Integer.valueOf(arr[1]);
for(int j = 2; j <= num * 2 ; j += 2) {
edges.put(Integer.valueOf(arr[j]),Integer.valueOf(arr[j+1]));
}
nodeList.add(new Node(Integer.valueOf(arr[0]), edges));
}
// ノード番号でソート処理
Collections.sort(nodeList, new NodeListComparator());
/*
* ここからダイクストラアルゴリズム
*/
// 出発地点を最小距離の0とする
nodeList.get(S).value = 0;
// 未確定のノードがなくなるまで反復処理
for(;;) {
long minValue = Long.MAX_VALUE;
int minNode = -1;
for(Node node : nodeList) {
if(!used[node.nodeNumber]) {
if(node.value < minValue) {
minValue = node.value;
minNode = node.nodeNumber;
}
}
}
// 対象ノードが見つからない場合終了
if(minValue == Long.MAX_VALUE) {
break;
}
used[minNode] = true;
// 対象ノード
Node node = nodeList.get(minNode);
for(Integer key : node.edges.keySet()) {
// 隣接するノード
Node nextNode = nodeList.get(key);
if(nextNode.value > node.value + node.edges.get(key)) {
nextNode.value = node.value + node.edges.get(key);
}
}
}
// 結果を出力
System.out.println("StartNode No." + S);
for(Node node : nodeList) {
System.out.println("No." + node.nodeNumber + ", minCost:" + node.value);
}
}
/*
* ここから内部クラス
*/
// ノードオブジェクト
public static class Node {
// ノードの最短距離
public long value;
// ノード番号
public int nodeNumber;
// キーを接続ノードとして、値を格納する辞書型リスト
public HashMap<Integer,Integer> edges;
public Node(int nodeNumber,HashMap<Integer,Integer> edges) {
//INFINITY
value = Long.MAX_VALUE;
this.nodeNumber = nodeNumber;
this.edges = edges;
}
}
// ノード番号でソートをする
public static class NodeListComparator implements Comparator<Node>{
@Override
public int compare(Node n1, Node n2) {
return n1.nodeNumber < n2.nodeNumber ? -1 : 1 ;
}
}
}
5
0 //出発地点
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3
StartNode No.0
No.0, minCost:0
No.1, minCost:2
No.2, minCost:2
No.3, minCost:1
No.4, minCost:3
5
3
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3
StartNode No.3
No.0, minCost:1
No.1, minCost:3
No.2, minCost:1
No.3, minCost:0
No.4, minCost:2
処理速度や効率性とかは考えずに実装したので、少し汚いコードになってしまいましたが、出力に関しては問題なさそうかな？
Pythonで同じようなプログラムを組んだことがあったので、特に難しく感じることはありませんでした。時間があれば他のアルゴリズムも実装してみたいかも。