問題描述： > 給定一個有向帶權圖 `G=(V，E)`，其中每條邊的權是一個非負實數。另外，給定 `V` 中的一個頂點，稱為源點。現在要計算從源點到所有其它各個頂點的最短路徑長度，這里的路徑長度是指路徑上經過的所有邊上的權值之和。 ---- **Dijkstra算法思想:** 按各個頂點與源點之間路徑長度的遞增次序，生成源點到各個頂點的最短路徑的方法，即先求出長度最短的一條路徑，再參照它求出長度次短的一條路徑，依此類推，直到從源點到其它各個頂點的最短路徑全部求出為止。 ---- **算法設計**： - 源點u 。集合S中的頂點到源點的最短路徑的長度已經確定，集合V-S中所包含的頂點到源點的最短路徑的長度待定。 - 特殊路徑：從源點出發只經過S中的點到達V-S中的點的路徑。 - 貪心策略：選擇特殊路徑長度最短的路徑，將其相連的V-S中的頂點加入到集合S中。 **求解步驟:** - 步驟1：設計合適的數據結構。帶權鄰接矩陣C，即如果< u, x >E，令 `C[u][x]=<u, x >` 的權值，否則，`C[u][x]=無窮`；采用數組dist來記錄從源點到其它頂點的最短路徑長度；采用數組p來記錄最短路徑； - 步驟2：初始化。令集合S={u}，對于集合V-S中的所有頂點x，設置`dist[x]=C[u][x]` ；如果頂點i與源點相鄰，設置 `p[i]=u` ，否則 `p[i]=-1`； - 步驟3：在集合V-S中依照貪心策略來尋找使得dist[x]具有最小值的頂點t，t就是集合V-S中距離源點u最近的頂點。 - 步驟4：將頂點t加入集合S中，同時更新集合V-S； - 步驟5：如果集合V-S為空，算法結束；否則，轉步驟6； - 步驟6：對集合V-S中的所有與頂點t相鄰的頂點x，如果`dist[x]>dist[t]+C[t][x]`，則`dist[x]=dist[t]+C[t][x]`并設置`p[x]=t`。轉步驟3。 ---- ```java public class Dijkstra { private static final int N = Integer.MAX_VALUE; private static final int[][] Graph = { {0, 1, 5, N, N, N, N, N, N}, {1, 0, 3, 7, 5, N, N, N, N}, {5, 3, 0, N, 1, 7, N, N, N}, {N, 7, N, 0, 2, N, 3, N, N}, {N, 5, 1, 2, 0, 3, 6, 9, N}, {N, N, 7, N, 3, 0, N, 5, N}, {N, N, N, 3, 6, N, 0, 2, 7}, {N, N, N, N, 9, 5, 2, 0, 4}, {N, N, N, N, N, N, 7, 4, 0}}; public static void main(String[] args) { dijkstra(0, Graph); } /** * Dijkstra最短路徑。 即圖中"節點vs"到其它各個節點的最短路徑。 * * @param vs 起始節點 * @param Graph 圖 */ public static void dijkstra(int vs, int[][] Graph) { int NUM = Graph[0].length; // 前驅節點數組 int[] prenode = new int[NUM]; // 最短距離數組 int[] mindist = new int[NUM]; // 該節點是否已經找到最短路徑 boolean[] find = new boolean[NUM]; int vnear = 0; for (int i = 0; i < mindist.length; i++) { prenode[i] = i; mindist[i] = Graph[vs][i]; find[i] = false; } find[vs] = true; for (int v = 1; v < Graph.length; v++) { // 每次循環求得距離vs最近的節點vnear和最短距離min int min = N; for (int j = 0; j < Graph.length; j++) { if (!find[j] && mindist[j] < min) { min = mindist[j]; vnear = j; } } find[vnear] = true; // 根據vnear修正vs到其他所有節點的前驅節點及距離 for (int k = 0; k < Graph.length; k++) { if (!find[k] && (min + Graph[vnear][k]) < mindist[k]) { prenode[k] = vnear; mindist[k] = min + Graph[vnear][k]; } } } for (int i = 0; i < NUM; i++) { System.out.println("v" + vs + "...v" + prenode[i] + "->v" + i + ", s=" + mindist[i]); } } } ``` ----