自己把Dijkstra的板子整理了一下，也方便自己后續做題，在此做個記錄。
Dijkstra基本上都會需要這些變量：
??????? dist[]：記錄各個節點到起始節點的最短權值
??????? path[]：記錄各個節點的上一個節點(用來聯系該節點到起始節點的路徑)
??????? start：源點序號
??????? end：結束頂點序號
????????weight[][]：存邊的權重
??????? visit[]：當前該頂點的最短路徑是否已求出，即訪沒訪問過
??????? shortPath[]：存儲每一次的最短路徑的長度
感覺這些變量到最后還是需要根據題意靈活的舍取吧。
然后簡單的解釋一下Dijkstra算法的具體思路，也方便后續理解代碼。
注意：???? 1.Dijkstra算法不適合帶負權圖。
??????????????? 2.計算單源最短路徑問題。
Dijkstra算法的本質其實是貪心，說的通俗易懂點就是以起始點(源點)為中心向外層擴展(bfs)，知道擴展到終點為止。
具體的算法過程如下：
??????? 聲明一個數組dist[]來保存源點到各個頂點的最短距離，聲明一個保存已經找到了最短路徑的頂點的集合T。然后初始化的時候，源點u的路徑權重被賦值為0，即dist[u] = 0，如果這個頂點u存在能直接到達的邊(u,v)，就把dist[v]設為weight[u][v]，（其中weight[i][j]表示(i,j)這條邊的權重），同時把所有其他（u不能直接到達的）頂點的路徑長度設為無窮大。初始時，集合T只有頂點s。
??????? 然后，從dist[]中選擇最小值，這個最小值就是源點u到該值對應的頂點的最短路徑，并且把該點加入到T中，此時我們就完成了第一個頂點的添加，除去源點，我們要加n-1個頂點。
??????? 接著，我們需要看看新加入的頂點是否可以到達其他頂點，并且還要看通過該頂點到達其他點的路徑長度是否比源點直接到達短，如果短的話，我們就替換這些頂點在dist中的值，也叫松弛操作。之后重復這一步就可以，直到T中包含了圖的所有頂點。
但是正常做題的時候好像并不會單獨創建一個集合去存頂點，一般都是用boolean visit[]數組，標記一下就行吧。
下面是我找到的Dijkstra板子：
public class 迪杰斯特拉 {static int M = 1000; // 表示兩個節點之間沒有路public static void main(String[] args) {int[][] weight = {{0, M, 10, M, 30, 100},{M, 0, 5, M, M, M},{M, M, 0, 50, M, M},{M, M, M, 0, M, 10},{M, M, M, 20, 0, 60},{M, M, M, M, M, 0}};int start = 0; // 表示從源點開始// 存儲每一次的最短路徑的長度int[] shortPath = Dijkstra(weight,start);for(int i = 0;i < shortPath.length;i ++) {// 說明start點到i點沒有最短路if (shortPath[i] == M) {continue;}System.out.println("從" + start+ "出發到" + i + "最短距離是：" + shortPath[i]);}}public static int[] Dijkstra(int [][]weight, int start) {int n = weight.length; // 頂點個數int[] shortPath = new int[n]; // 保存start點到其他各點的最短路徑String[] path = new String[n]; // 存儲每一步，保存start到其他各點的字符串表示for(int i = 0;i < n;i ++) {path[i] = start + "->" + i;}boolean[] visit = new boolean[n]; // 標記當前該頂點的最短路徑是否已求出，1表示已求出// 進行初始化shortPath[start] = 0;visit[start] = true;for(int cnt = 1;cnt < n; cnt ++) { // 加入其余n-1個節點int k = 0; // 選出一個距離初始頂點最近的未被標記的點int min = Integer.MAX_VALUE;for(int i = 0;i < n;i ++) {// 表示該點未確定最短路徑，并且start到該點有直接連接if (!visit[i] && weight[start][i] < min) {min = weight[start][i];k = i;}}// 把剛剛新選出的頂點標記為以求出最短路徑，并且路徑長度為minvisit[k] = true;shortPath[k] = min;// 這個時候k作為中轉節點，來進一步判斷start到未訪問的其他頂點的距離for(int i = 0;i < n;i ++) {// 表示由start到頂點i有一條路是經過頂點k的，并且要比start直接到達頂點i的距離要短，然后就更新，也叫松弛操作if (!visit[i] && weight[start][k] + weight[k][i] < weight[start][i]) {weight[start][i] = weight[start][k] + weight[k][i];path[i] = path[k] + "->" + i;}}}for(int i = 0;i < n;i ++) {if (shortPath[i] == M) {continue;}System.out.println("從" + start + "出發到" + i + "的最短路徑：" + path[i]);}return shortPath;}
}
)
