目錄

1. 什么是賦權最短路徑

2. 賦權最短路徑中的關鍵概念

3. Dijkstra 算法的基本思想

4. Dijkstra 算法實現（Java）

---

1. 什么是賦權最短路徑

在圖論中，最短路徑問題是指在圖中尋找兩點之間路徑總權重最小的路徑問題。如果圖的每條邊都帶有權值（weight），這種圖稱為賦權圖（Weighted Graph）。

2. 賦權最短路徑中的關鍵概念

在賦權最短路徑算法中，常用的幾個重要概念包括：

• 頂點（Vertex/Node） 圖的基本組成元素，用于表示位置或對象。

• 邊（Edge） 頂點之間的連接關系，可能是有向的（Directed）或無向的（Undirected）。

• 權重（Weight） 與每條邊相關聯的數值，表示從一個頂點到另一個頂點的“代價”，可能是時間、距離、費用等。

• 路徑（Path） 由一系列頂點和邊構成的通路。

• 路徑長度（Path Length） 路徑上所有邊的權重之和。

• 前驅節點（Predecessor Node） 在最短路徑中，到達某個頂點前的上一個頂點，用于回溯構建路徑。

• 松弛操作（Relaxation） 如果通過某條邊能找到更短的路徑，則更新目標頂點的最短距離和前驅節點的過程。

3. Dijkstra 算法的基本思想

Dijkstra 算法由 Edsger W. Dijkstra 在 1956 年提出，是解決單源非負權重最短路徑問題的經典算法。 其核心思想是：

1. 初始化

   • 將源點的最短距離設置為 0，其他頂點設置為無窮大（Integer.MAX_VALUE）。

   • 使用一個優先隊列按當前已知的最短距離排序。

2. 迭代選擇最近的未處理頂點

   • 從優先隊列中取出當前距離最小的頂點 u。

   • 將其標記為“已處理”，不再更新它的距離。

3. 松弛鄰居節點

   • 對于 u 的所有鄰接頂點 v，計算 u 到 v 的新距離 newDist = dist[u] + weight(u, v)。

   • 如果 newDist < dist[v]，則更新 dist[v] = newDist，并記錄 u 為 v 的前驅節點。

4. 重復步驟 2 和 3，直到所有頂點都處理完，或者優先隊列為空。

算法特性：

• 時間復雜度：使用優先隊列時為 O(E log V)，其中 E 是邊數，V 是頂點數。

• 不能處理含有負權邊的圖（會導致錯誤結果）。

• 保證每次取出的頂點，其最短距離已經確定。

4. Dijkstra 算法實現（Java）

下面給出基于上述思路的完整 Java 實現代碼，代碼中包含了節點（Node）、邊（Edge）的數據結構定義，以及 Dijkstra 算法的執行與路徑回溯功能。

import java.util.*;class Node {public String name;          // 頂點名稱public List<Edge> adj;    // 鄰接頂點列表boolean processed;        // 是否已處理public int dist;  // 初始距離設為無窮大public Node preNode;         // 最短路徑上的前驅頂點public Node(String name) {this.name = name;this.adj = new ArrayList<>();this.processed = false;this.dist = Integer.MAX_VALUE;this.preNode = null;}// 添加鄰接邊public void addEdge(Node to, int weight) {this.adj.add(new Edge(this, to, weight));}
}// 邊類定義
class Edge {Node from;Node to;   // 目標節點int weight;    // 邊權重public Edge(Node from, Node to, int weight) {this.from = from;this.to = to;this.weight = weight;}
}public class GraphShortPath {public static final int INFINITY = Integer.MAX_VALUE;/*** 計算單源無權最短路徑* @param source 源頂點*/public static void unweighted(Node source) {Queue<Node> queue = new LinkedList<>();source.dist = 0;             // 源點距離設為0queue.add(source);               // 源點入隊while (!queue.isEmpty()) {Node current = queue.poll();// 遍歷所有鄰接頂點for (Edge edge : current.adj) {Node neighbor = edge.to;// 如果頂點未被訪問過if (neighbor.dist == INFINITY) {neighbor.dist = current.dist + 1;    // 更新距離neighbor.preNode = current;             // 記錄路徑queue.add(neighbor);               // 鄰接點入隊}}}}/*** Dijkstra 算法 計算 單源賦權最短路徑* @param source*/public static void dijkstra(Node source) {PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(node -> node.dist));source.dist = 0;queue.add(source);while (!queue.isEmpty()) {Node current = queue.poll();if (current.processed) continue;current.processed = true;for (Edge edge : current.adj) {Node neighbor = edge.to;if (neighbor.processed) continue;long newDist = (long) current.dist + edge.weight;if (newDist > Integer.MAX_VALUE) continue;if (newDist < neighbor.dist) { // 發現更短路徑則更新 neighbor.dist = (int) newDist;neighbor.preNode = current;queue.add(neighbor);}}}}/*** 重構從源點到目標頂點的最短路徑* @param to 目標頂點* @return 路徑頂點列表*/public static List<Node> reconstructPath(Node to) {List<Node> path = new ArrayList<>();// 如果目標頂點不可達if (to.dist == INFINITY) {return path;}// 從目標頂點回溯到源頂點for (Node v = to; v != null; v = v.preNode) {path.add(v);}// 反轉路徑：從源頂點到目標頂點Collections.reverse(path);return path;}/*** 打印最短路徑結果* @param vertices 頂點列表*/public static void printResults(List<Node> vertices) {System.out.println("頂點\t距離\t前驅\t路徑");System.out.println("--------------------------------------");for (Node v : vertices) {System.out.printf("%s\t%d\t%s\t",v.name,v.dist,(v.preNode != null) ? v.preNode.name : "null");// 打印路徑List<Node> path = reconstructPath(v);if (path.isEmpty()) {System.out.print("不可達");} else {for (int i = 0; i < path.size(); i++) {if (i > 0) System.out.print(" → ");System.out.print(path.get(i).name);}}System.out.println();}}// 測試用例public static void main(String[] args) {// 創建頂點Node v1 = new Node("圖書館");Node v2 = new Node("教學樓A");Node v3 = new Node("教學樓B");Node v4 = new Node("食堂");Node v5 = new Node("體育館");Node v6 = new Node("宿舍");Node v7 = new Node("校門");// 構建校園地圖的無向圖v1.addEdge(v2,5);v1.addEdge(v4,1);v2.addEdge(v1,2);v2.addEdge(v3,3);v2.addEdge(v5,5);v3.addEdge(v2,4);v3.addEdge(v6,3);v4.addEdge(v1,3);v4.addEdge(v5,5);v4.addEdge(v7,2);v5.addEdge(v2,1);v5.addEdge(v4,1);v5.addEdge(v6,3);v6.addEdge(v3,2);v6.addEdge(v5,3);v6.addEdge(v6,4);v7.addEdge(v4,2);v7.addEdge(v6,2);List<Node> campus = Arrays.asList(v1, v2, v3, v4, v5, v6, v7);// 從圖書館出發計算最短路徑
//        unweighted(v1);// 從圖書館出發計算最短路徑dijkstra(v1);// 打印結果printResults(campus);// 額外測試：從圖書館到校門的最短路徑System.out.println("\n從圖書館到校門的最短路徑:");List<Node> pathToGate = reconstructPath(v7);for (Node v : pathToGate) {System.out.print(v.name + (v != v7 ? " → " : ""));}}
}

• 運行結果

頂點?? ?距離?? ?前驅?? ?路徑
--------------------------------------
圖書館?? ?0?? ?null?? ?圖書館
教學樓A?? ?5?? ?圖書館?? ?圖書館 → 教學樓A
教學樓B?? ?7?? ?宿舍?? ?圖書館 → 食堂 → 校門 → 宿舍 → 教學樓B
食堂?? ?1?? ?圖書館?? ?圖書館 → 食堂
體育館?? ?6?? ?食堂?? ?圖書館 → 食堂 → 體育館
宿舍?? ?5?? ?校門?? ?圖書館 → 食堂 → 校門 → 宿舍
校門?? ?3?? ?食堂?? ?圖書館 → 食堂 → 校門從圖書館到校門的最短路徑:
圖書館 → 食堂 → 校門