[Java]ダイクストラ法で最短経路を見つけてみる

## 経緯
競技プログラミング練習用にJavaでダイクストラ法を実装してみました。
変数名を適当に付けたりしているので間違い・気になるところあればご指摘ください。

## ダイクストラ法とは？
ざっくり簡単に言うと、経路の最短距離を用いるために利用されるアルゴリズム。
詳しい説明に関してはwikipediaの参照をお願いします。   
## 求め方
例題として、この問題で考えてみる。
https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_B&lang=jp

以下の重み付きグラフで最短経路を求めてみる。
・出発地点はノード０。
・変数Dminは出発地点からの最短距離。
・出発地点のDminを０として、他ノードにはINF値を入れておく。
![dijkstra.drawio (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3083608/99b7cfef-bcfb-f415-a35b-c4f85f5d650c.png)

ここからダイクストラ法を用いて、最短距離を見つけていく。

(1回目のループ処理)
1. まだ訪れていないノードの中で、Dminが最小になるのはノード０。
2. ノード０を訪問済みとして、ノード０と隣接するノード(ノード１、ノード２、ノード３)までかかる距離を計測する。
3. 計測した距離が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回目の更新後がこちら。
![dijkstra.drawio (7).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3083608/39c90acf-3699-b797-91b5-a09be16823b6.png)


(2回目のループ処理)
1. まだ訪れていないノードの中で、Dminが最小になるのはノード３。
2. ノード３を訪問済みとして、ノード３と隣接するノード(ノード１、ノード４)までかかる距離を計測する。
3. 計測した距離がDmin以下、つまり現状の最短距離よりも短ければ、その値で更新する。
4.未訪問ノードがなければ、処理を終了。あれば(1)の処理へ。

(3)の処理後、隣接するノードのDminは
Dmin[1] = 2
Dmin[2] = 2
Dmin[4] = 3

ノード１に関しては、元々の最短距離が2であるのに対して、ノード０-３-２経由だと距離が5となるので、更新はしない。

2回目の更新後がこちら。
![dijkstra.drawio (6).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3083608/8aeb99ad-8bef-ac75-c4ab-9e6d5c19002b.png)


3回目(更新なし)。
![dijkstra.drawio (9).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3083608/0d130440-fe96-695d-11f7-2a77d001d396.png)

4回目。
![dijkstra.drawio (10).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3083608/54fa412d-70dc-f613-6b24-daaa43d6d51b.png)

5回目。
![dijkstra.drawio (11).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3083608/3ee8c2cb-ba2f-ebf6-1296-9eaf910918d1.png)

未訪問のノードがなくなったので、処理を終了。
ノード０から各ノードの最短距離が求められる。これをJavaで書いてみる。

## コーディング
上の例題に加えて、出発地点Sも変更できるようにする。

```Java:Dijkstra.java
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 ;
		}
		
	}

}
```

```java:入力例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
```

```java:出力例
StartNode No.0
No.0, minCost:0
No.1, minCost:2
No.2, minCost:2
No.3, minCost:1
No.4, minCost:3
```

```java:入力例2
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
```
```java:出力例2
StartNode No.3
No.0, minCost:1
No.1, minCost:3
No.2, minCost:1
No.3, minCost:0
No.4, minCost:2
```

処理速度や効率性とかは考えずに実装したので、少し汚いコードになってしまいましたが、出力に関しては問題なさそうかな？

Pythonで同じようなプログラムを組んだことがあったので、特に難しく感じることはありませんでした。時間があれば他のアルゴリズムも実装してみたいかも。