Java 實現 Dijkstra 最短路徑算法：核心邏輯、源碼完整實現與測試驗證

Java 實現 Dijkstra 最短路徑算法：核心邏輯、源碼完整實現與測試驗證

Dijkstra 算法解決有向圖單源最短路徑問題，以起點為中心向外層層擴展。本文提供介面定義、數據結構設計、核心遞歸邏輯、路徑回溯組裝、完整可運行代碼與測試用例。

問題建模

• 節點：正整數 ID（1, 2, 3...）。
• 邊：相鄰節點間距離（正整數）。
• 輸入：`Map> stepLength`，`stepLength.get(u).get(v) = w` 表示 u→v 距離 w。
• 輸出：`MinStep{reachable, minStep, path}`，含最短距離與經過節點列表。

核心數據結構

// 返回結果
public class MinStep {
    private boolean reachable;
    private int minStep;
    private List path;  // 起點→終點節點序列
}

// 算法過程中每個節點的最優前驅與距離
public class PreNode {
    private int preNode;   // 最短路徑下的前一個節點
    private int nodeStep;  // 起點到該節點的最短距離
}

算法狀態變量

private Map> graph;  // 輸入圖
private int nodeCount;                               // 節點總數
private Set visited;                        // 已確定最短路徑的節點
private Map shortest;              // 節點→{前驅,距離}
private Deque frontier;                     // 待處理節點隊列
private int start, end;                              // 起終點

核心遞歸步驟 step()

1. **終止條件**：`frontier` 為空 或 `visited.size() == nodeCount` → 返回。
2. **取出當前節點** `u = frontier.pollFirst()`。
3. **當前最短距離** `dist = shortest.get(u).nodeStep`（起點為 0）。
4. **遍歷鄰居** `v`：
     `newDist = dist + weight(u,v)`
     若 `v` 未在 `shortest` 或 `newDist < shortest.get(v).nodeStep` → 更新 `shortest[v] = new PreNode(u, newDist)`。
     若 `v` 未訪問且不在 `frontier` → 加入 `frontier`。
5. **標記訪問** `visited.add(u)`。
6. **遞歸處理下一節點** `step()`。

路徑回溯組裝

private MinStep buildResult() {
    MinStep ms = new MinStep();
    ms.setReachable(true);
    ms.setMinStep(shortest.get(end).nodeStep);
    LinkedList path = new LinkedList<>();
    int cur = end;
    path.addFirst(cur);
    while (shortest.containsKey(cur)) {
        cur = shortest.get(cur).preNode;
        path.addFirst(cur);
    }
    ms.setPath(path);
    return ms;
}

完整實現 DistanceDijkstraImpl

public class DistanceDijkstraImpl implements Distance {
    public MinStep getMinStep(int start, int end, Map> graph) {
        this.graph = graph;
        this.nodeCount = graph != null ? graph.size() : 0;
        if (graph == null || !graph.containsKey(start) || !graph.containsKey(end)) {
            return MinStep.UNREACHABLE;
        }
        init(start, end);
        step();
        return shortest.containsKey(end) ? buildResult() : MinStep.UNREACHABLE;
    }
    // ... init/step/buildResult 如上
}

測試用例：經典 6 節點圖

public class DijkstraTest {
    public static void main(String[] args) {
        Map> g = new HashMap<>();
        // 1→2(7) 1→3(9) 1→6(14)
        put(g, 1, 2, 7); put(g, 1, 3, 9); put(g, 1, 6, 14);
        // 2→1(7) 2→3(10) 2→4(15)
        put(g, 2, 1, 7); put(g, 2, 3, 10); put(g, 2, 4, 15);
        // 3→1(9) 3→2(10) 3→4(11) 3→6(2)
        put(g, 3, 1, 9); put(g, 3, 2, 10); put(g, 3, 4, 11); put(g, 3, 6, 2);
        // 4→2(15) 4→3(11) 4→5(5)
        put(g, 4, 2, 15); put(g, 4, 3, 11); put(g, 4, 5, 5);
        // 5→4(5) 5→6(9)
        put(g, 5, 4, 5); put(g, 5, 6, 9);
        // 6→1(14) 6→3(2) 6→5(9)
        put(g, 6, 1, 14); put(g, 6, 3, 2); put(g, 6, 5, 9);

        Distance dijkstra = new DistanceDijkstraImpl();
        MinStep result = dijkstra.getMinStep(1, 5, g);
        System.out.println(result);  // {reachable=true, minStep=20, path=[1, 3, 6, 5]}
    }
    static void put(Map> g, int u, int v, int w) {
        g.computeIfAbsent(u, k -> new HashMap<>()).put(v, w);
    }
}

輸出驗證

{reachable=true, minStep=20, path=[1, 3, 6, 5]}

路徑 1→3(9) → 6(2) → 5(9) = 20，符合教科書標準答案。

複雜度與優化方向

• 時間複雜度：O(V²) 陣列實現 / O(E log V) 優先隊列（堆）優化。
• 空間複雜度：O(V)。
• 負權邊不適用 → 改用 Bellman-Ford 或 SPFA。
• 全源最短路徑 → Floyd-Warshall O(V³) 或 Johnson O(V E log V)。

實際應用場景

1. 導航系統路徑規劃（道路網絡權重為距離/時間）。
2. 網路路由協議（OSPF/IS-IS 鏈路狀態路由）。
3. 遊戲地圖尋路（A* 為 Dijkstra + 啟發式優化）。
4. 依賴解析、編譯順序、供應鏈優化等圖論建模問題。