Java 實現 Dijkstra 最短路徑算法完整教程與代碼詳解

算法原理

Dijkstra 算法是解決有向圖單源最短路徑的經典貪心算法。核心思想：按路徑長度遞增順序逐步確定各頂點的最短路徑，每次選擇當前未訪問頂點中距離源點最近的頂點，並以此為中介點鬆弛其他頂點的距離。

算法步驟

1. 初始化：源點距離為 0，其餘頂點距離設為無窮大（代碼中用 10000 表示）；所有頂點標記為未訪問
2. 選擇最近頂點：從未訪問頂點中選擇距離源點最小的頂點 k
3. 標記訪問：將 k 標記為已訪問，其最短路徑已確定
4. 鬆弛鄰接頂點：以 k 為中介點，更新未訪問頂點的距離：if (dist[start][k] + weight[k][i] < dist[start][i])
5. 重複執行：循環 n-1 次直到所有頂點均被訪問

完整 Java 實現代碼

package com.algorithm.impl;

public class Dijkstra {
    private static final int INF = 10000; // 表示不可達

    public static void main(String[] args) {
        // 測試圖 1
        int[][] weight1 = {
            {0, 3, INF, 7, INF},
            {3, 0, 4, 2, INF},
            {INF, 4, 0, 5, 4},
            {7, 2, 5, 0, 6},
            {INF, INF, 4, 6, 0}
        };

        // 測試圖 2（有向圖）
        int[][] weight2 = {
            {0, 10, INF, 30, 100},
            {INF, 0, 50, INF, INF},
            {INF, INF, 0, INF, 10},
            {INF, INF, 20, 0, 60},
            {INF, INF, INF, INF, 0}
        };

        int start = 0;
        int[] shortPath = dijkstra(weight2, start);
        
        for (int i = 0; i < shortPath.length; i++) {
            System.out.println("從 " + start + " 出發到 " + i + " 的最短距離為：" + shortPath[i]);
        }
    }

    public static int[] dijkstra(int[][] weight, int start) {
        int n = weight.length;
        int[] shortPath = new int[n];      // 最短路徑長度
        String[] path = new String[n];     // 路徑字符串記錄
        int[] visited = new int[n];        // 訪問標記

        // 初始化路徑記錄
        for (int i = 0; i < n; i++) {
            path[i] = start + "-->" + i;
        }

        // 源點初始化
        shortPath[start] = 0;
        visited[start] = 1;

        // 主循環：加入 n-1 個頂點
        for (int count = 1; count < n; count++) {
            int k = -1;
            int dmin = Integer.MAX_VALUE;

            // 選擇距離最近的未訪問頂點
            for (int i = 0; i < n; i++) {
                if (visited[i] == 0 && weight[start][i] < dmin) {
                    dmin = weight[start][i];
                    k = i;
                }
            }

            // 標記並記錄最短距離
            shortPath[k] = dmin;
            visited[k] = 1;

            // 以 k 為中介點鬆弛
            for (int i = 0; i < n; i++) {
                if (visited[i] == 0 && 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++) {
            System.out.println("從 " + start + " 出發到 " + i + " 的最短路徑為：" + path[i]);
        }
        System.out.println("=====================================");

        return shortPath;
    }
}

運行結果分析

從 0 出發到 0 的最短路徑為：0-->0
從 0 出發到 1 的最短路徑為：0-->1
從 0 出發到 2 的最短路徑為：0-->3-->2
從 0 出發到 3 的最短路徑為：0-->3
從 0 出發到 4 的最短路徑為：0-->3-->2-->4
=====================================
從 0 出發到 0 的最短距離為：0
從 0 出發到 1 的最短距離為：10
從 0 出發到 2 的最短距離為：50
從 0 出發到 3 的最短距離為：30
從 0 出發到 4 的最短距離為：60

關鍵技術點

• 鄰接矩陣表示：二維數組存儲圖的邊權重，INF 表示無直接連接
• 路徑重構：path 數組記錄完整路徑字符串，便於調試與展示
• 原地更新：直接修改 weight[start][i] 存儲當前最短距離，節省空間
• 有向圖支持：矩陣非對稱結構天然支持有向邊

複雜度分析

• 時間複雜度：O(V²) —— 適合稠密圖；使用優先隊列可優化至 O(E log V)
• 空間複雜度：O(V) —— 距離、路徑、訪問標記數組

擴展建議

1. 使用 PriorityQueue 優化選擇最近頂點過程
2. 改用鄰接表存儲稀疏圖
3. 增加負權重檢測（Dijkstra 不支持負權邊）
4. 封裝為通用工具類，支持泛型頂點類型

總結

本文提供了 Dijkstra 算法的完整 Java 實現，包含核心邏輯解析、可運行代碼與結果驗證。理解此算法對掌握圖論基礎、網絡路由、地圖導航等領域具有重要意義。