Dijkstra算法（單源路徑最短算法）

1. Dijstra算法求解的是圖中一個頂點到其餘頂點的最短路徑

Dijstra算法思想：設有兩個頂點集合S和T，集合S中存放的圖中已經找到最短路徑的頂點，集合T中存放圖中剩餘頂點，初始狀态的時候，集合S中隻包含源點v0，然後不斷從集合T中選取到頂點v0路徑長度最短的頂點v并入到集合S中去，集合S每并入一個新的頂點，都要修改頂點v0到集合T中頂點的最短路徑長度值

總結起來我感覺主要有兩步：

① 選取源點到其餘頂點路徑最短的那個頂點

② 每選取一個頂點都要更新從源點到其餘頂點的路徑，因為每加入一個頂點，有可能使源點到其餘頂點通過這個頂點的作用路徑變得更短，比如源點0到3的路徑一開始為4但是并入1節點之後那麼路徑為3變短了是以需要更新到3頂點的最短路徑

2. 我感覺Dijkstra算法與Prim最小生成樹的算法很類似，在程式設計方面上的差別：Prim算法中的d[]數組記錄的是其餘頂點到目前頂點的最短路徑，而Dijkstra算法記錄的是源點到其餘頂點的最短路徑，這個差別導緻在更新d[]數組的時候的值也是不一樣的，我們可以類比這兩個算法來進一步了解其中的思想

下面是具體的有向有權的的一個例子：

假如以頂點0作為源點那麼首先選取與頂點0相接的頂點，在循環中判斷頂點0到相接的頂點的距離是否比之前源點到達這些頂點的路徑是更短，可以發現路徑是變短了，因為之前是沒有路徑到達1,3,4頂點的是以需要更新d[]數組中對應的三個頂點，下一次選取源點到達其餘頂點中路徑最短的，可以發現0到1頂點路徑是最短的，是以選擇1頂點，重複上面的步驟即可，可以發現1與3頂點相接，那麼判斷一下1頂點到3頂點的路徑是否比之前源點到3的路徑更短發現是變短了那麼更新，以此類推其餘頂點也是一樣的道理

測試資料如下：

6
8
0 1 1
0 3 4
0 4 4
1 3 2
2 5 1
3 2 2
3 4 3
4 5 3
           

3. 具體的代碼如下：

import java.util.Arrays;
import java.util.Scanner;
public class Main {
	static int n = 0;
	static int edges = 0;
	static int graph[][];
	static int visit[];
	static int d[];
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.println("輸入頂點數: ");
		n = sc.nextInt();
		graph = new int[n][n];
		visit = new int[n];
		d = new int[n];
		System.out.println("輸入邊數: ");
		edges = sc.nextInt();
		System.out.println("輸入起始頂點, 結束頂點和頂點之間邊的權重: ");
		for(int i = 0; i < edges; i++){
			int start = sc.nextInt();
			int end = sc.nextInt();
			int weight = sc.nextInt();
			graph[start][end] = weight;
		}
		//輸入需要求解的源點
		int u = sc.nextInt();
		int res[] = Dijkstra(u);
		for(int i = 0; i < res.length; i++){
			System.out.print(res[i] + " ");
		}
		sc.close();
	}
	
	private static int[] Dijkstra(int u) {
		Arrays.fill(d, Integer.MAX_VALUE);
		d[u] = 0;
		for(int i = 0; i < n; i++){
			u = -1;
			int min = Integer.MAX_VALUE;
			for(int j = 0; j < n; j++){
				if(visit[j] == 0 && d[j] < min){
					u = j;
					min = d[j];
				}
			}
			if(u == -1) return d;
			visit[u] = 1;	
			for(int v = 0; v < n; v++){
				if(visit[v] == 0 && graph[u][v] != 0 && d[v] > d[u] + graph[u][v]){
					d[v] = d[u] + graph[u][v];
				}
			}
		}
		return d;
	}
}