Dijkstra 最短路徑算法 Java 完整實現與解析

算法背景與應用場景

Dijkstra 算法是解決單源點最短路徑問題的經典算法，廣泛應用於導航系統、網絡路由、城市交通規劃等領域。本文提供完整的 Java 實現代碼，並詳細解析核心邏輯。

核心數據結構設計

// 邊類：表示圖中的有向邊
static class Side {
    int from, to, weight;
    Side(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
}

算法實現步驟

1. 初始化階段

// 頂點集合
int[] nodes = {0, 1, 3, 2, 4, 5, 6};

// 圖的邊集合（鄰接表表示）
List<Side> map = new ArrayList<>();
map.add(new Side(0, 1, 10));
map.add(new Side(0, 3, 30));
map.add(new Side(0, 4, 100));
map.add(new Side(1, 2, 50));
map.add(new Side(2, 4, 10));
map.add(new Side(3, 2, 20));
map.add(new Side(3, 4, 60));
map.add(new Side(4, 5, 50));
map.add(new Side(3, 5, 60));
map.add(new Side(5, 6, 10));
map.add(new Side(3, 6, 80));

// 紅點集：已確定最短路徑的頂點
List<Integer> redAgg = new ArrayList<>();
redAgg.add(nodes[0]);  // 起點加入紅點集

// 藍點集：未確定最短路徑的頂點
List<Integer> blueAgg = new ArrayList<>();
for (int i = 1; i < nodes.length; i++) {
    blueAgg.add(nodes[i]);
}

// 父節點記錄：重構最短路徑
Side[] parents = new Side[nodes.length];

2. 核心迭代邏輯

while (!blueAgg.isEmpty()) {
    int minDist = Integer.MAX_VALUE;
    int closestNode = -1;
    Side bestEdge = null;

    // 遍歷紅點集的所有出邊，找到距離最近的藍點
    for (int redNode : redAgg) {
        for (Side edge : map) {
            if (edge.from == redNode && blueAgg.contains(edge.to)) {
                int dist = getDistance(redNode) + edge.weight;
                if (dist < minDist) {
                    minDist = dist;
                    closestNode = edge.to;
                    bestEdge = edge;
                }
            }
        }
    }

    // 將最近藍點移入紅點集
    if (closestNode != -1) {
        redAgg.add(closestNode);
        blueAgg.remove(Integer.valueOf(closestNode));
        parents[closestNode] = bestEdge;
    }
}

3. 路徑重構與結果輸出

// 計算到指定頂點的最短距離
int getDistance(int node) {
    if (node == nodes[0]) return 0;
    Side edge = parents[node];
    return edge == null ? Integer.MAX_VALUE : getDistance(edge.from) + edge.weight;
}

// 輸出所有頂點的最短路徑
for (int node : nodes) {
    System.out.println("頂點 " + node + " 最短距離: " + getDistance(node));
    printPath(node);
}

void printPath(int node) {
    if (node == nodes[0]) {
        System.out.print(node);
        return;
    }
    Side edge = parents[node];
    if (edge != null) {
        printPath(edge.from);
        System.out.print(" -> " + node);
    }
}

關鍵優化點

• 優先隊列優化：使用 PriorityQueue 可將時間複雜度從 O(V²) 降至 O(E log V)
• 鄰接表存儲：比鄰接矩陣更節省稀疏圖的空間
• 路徑記錄：通過父節點數組實現路徑回溯

完整可運行代碼結構

package sinboy.datastructure;

import java.util.*;

public class Dijkstra {
    static class Side { /* ... */ }
    
    static List<Side> map;
    static List<Integer> redAgg, blueAgg;
    static Side[] parents;
    
    public static void main(String[] args) {
        // 初始化圖數據
        // 執行算法
        // 輸出結果
    }
    
    // 輔助方法...
}

該實現展示了 Dijkstra 算法的貪心策略本質：每次選擇當前已知最短路徑的頂點擴展，保證最終得到全局最優解。理解此算法為學習 A*、N-最短路徑等進階算法奠定基礎。