Dijkstra 算法求網絡最短路徑：C 語言完整實現與圖解

Dijkstra 算法求網絡最短路徑：C 語言完整實現與圖解

算法核心思想

從源點 v0 出發，維護一個 dist[] 數組記錄當前已知最短路徑長度，每輪選取「未確定且距離最小」的頂點加入確定集合，並用其鬆弛鄰接邊。適用於無負權邊的有向/無向圖。

關鍵數據結構

• cost[N][N]：鄰接矩陣，I=9999 表示無邊（無窮大）。
• dist[N]：源點到各頂點當前最短距離。
• final[N]：標記該頂點最短路徑是否已確定。

完整代碼 (C 語言)

#include 
#define TRUE 1
#define FALSE 0
#define INF 9999
#define N 20

int cost[N][N] = {
    {0,3,INF,INF,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
    {3,0,5,INF,INF,INF,6,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
    {INF,5,0,4,INF,INF,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
    {INF,INF,4,0,2,INF,INF,INF,6,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
    {INF,INF,INF,2,0,INF,INF,INF,INF,7,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
    {1,INF,INF,INF,INF,0,1,INF,INF,INF,2,INF,INF,INF,INF,INF,INF,INF,INF,INF},
    {INF,6,INF,INF,INF,1,0,6,INF,INF,INF,7,INF,INF,INF,INF,INF,INF,INF,INF},
    {INF,INF,1,INF,INF,INF,6,0,2,INF,INF,INF,3,INF,INF,INF,INF,INF,INF,INF},
    {INF,INF,INF,6,INF,INF,INF,2,0,8,INF,INF,INF,4,INF,INF,INF,INF,INF,INF},
    {INF,INF,INF,INF,7,INF,INF,INF,8,0,INF,INF,INF,INF,5,INF,INF,INF,INF,INF},
    {INF,INF,INF,INF,INF,2,INF,INF,INF,INF,0,4,INF,INF,INF,3,INF,INF,INF,INF},
    {INF,INF,INF,INF,INF,INF,7,INF,INF,INF,4,0,3,INF,INF,INF,4,INF,INF,INF},
    {INF,INF,INF,INF,INF,INF,INF,3,INF,INF,INF,3,0,3,INF,INF,INF,5,INF,INF},
    {INF,INF,INF,INF,INF,INF,INF,INF,4,INF,INF,INF,3,0,7,INF,INF,INF,2,INF},
    {INF,INF,INF,INF,INF,INF,INF,INF,INF,5,INF,INF,INF,7,0,INF,INF,INF,INF,3},
    {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,3,INF,INF,INF,INF,0,5,INF,INF,INF},
    {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,4,INF,INF,INF,5,0,8,INF,INF},
    {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,5,INF,INF,INF,8,0,6,INF},
    {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,2,INF,INF,INF,6,0,4},
    {INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,3,INF,INF,INF,4,0}
};

int dist[N];
int final[N];

int main() {
    int v0 = 0; // 'A' - 'A' = 0
    // 初始化
    for (int v = 0; v < N; v++) {
        final[v] = FALSE;
        dist[v] = cost[v0][v];
    }
    final[v0] = TRUE; // 源點距離為 0 已確定

    // 進行 N-1 輪選取
    for (int i = 0; i < N-1; i++) {
        int min = INF, v = -1;
        // 選未確定且距離最小的頂點
        for (int w = 0; w < N; w++)
            if (!final[w] && dist[w] < min) { min = dist[w]; v = w; }
        if (v == -1) break; // 剩餘不可達
        final[v] = TRUE;
        // 鬆弛 v 的所有出邊
        for (int w = 0; w < N; w++)
            if (!final[w] && dist[v] + cost[v][w] < dist[w])
                dist[w] = dist[v] + cost[v][w];
    }

    // 輸出結果
    for (int i = 0; i < N; i++)
        printf("%c->%c: %2d\t", 'A'+v0, 'A'+i, dist[i]);
    return 0;
}

運行結果解讀

程式輸出源點 A 到所有節點的最短距離，例如：

A->A:  0    A->B:  3    A->C:  8    A->D: 12    A->E: 14    ...

可手動驗證：A→F(1)→G(1)→H(6)→I(2)→J(8) = 18，與輸出一致。

複雜度與優化

• 鄰接矩陣 + 線性找最小：O(N^2)，適合稠密圖（N ≤ 2000）。
• 稀疏圖改用 鄰接表 + 優先隊列（最小堆）：O((V+E) log V)。
• 負權邊需用 Bellman-Ford 或 SPFA。

常見錯誤

1. 忘記初始化 final[v0]=TRUE，導致源點被重複選取。
2. INF 設太小導致路徑長度溢位判斷錯誤；建議 0x3f3f3f3f 或 1e9。
3. 鬆弛條件漏寫 !final[w]，導致已確定節點被更新。