C語言實現Floyd-Warshall算法求全源最短路徑

Floyd-Warshall算法C語言實現：全源最短路徑問題詳解

Floyd-Warshall算法是解決圖中任意兩點最短路徑的經典動態規劃算法，時間複雜度O(V³)，適用於稠密圖。本文提供基於鄰接矩陣的完整C語言實現，包含路徑重構、路徑長度矩陣維護等核心邏輯。

算法核心思想

動態規劃狀態定義：D[i][j]表示從頂點i到j的最短路徑長度，path[i][j]記錄i到j最短路徑上i的下一個頂點。核心遞推：

D[i][j] = min(D[i][j], D[i][k] + D[k][j])  // 允許經過頂點k
path[i][j] = path[i][k]  // 更新下一跳頂點

數據結構設計

void Floyd(MGraph *G, int path[][MAX_VERTICES], int D[][MAX_VERTICES], int n) {
    int i, j, k;
    
    // === 初始化階段 ===
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (G->A[i][j] < INF) {
                D[i][j] = G->A[i][j];
                path[i][j] = j;  // 直接可達，下一跳為j
            } else {
                D[i][j] = INF;
                path[i][j] = -1; // 不可達
            }
        }
        D[i][i] = 0;      // 自環距離為0
        path[i][i] = i;   // 自己到自己下一跳是自己
    }
    
    // === 核心動態規劃：三層循環 ===
    for (k = 0; k < n; k++) {        // 中間頂點
        for (i = 0; i < n; i++) {    // 起點
            for (j = 0; j < n; j++) { // 終點
                if (D[i][k] + D[k][j] < D[i][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                    path[i][j] = path[i][k];  // 關鍵：下一跳更新為i->k的第一跳
                }
            }
        }
    }
}

路徑重構函數

 %c", vertices[current]);
    }
    printf("\n");
}

測試用例與驗證

輸出結果解析
最短路徑長度矩陣:
  0  12  18  15  17  23
 12   0  10   3  13   5
 18  10   0  13  21  11
 15   3  13   0  16   8
 17  13  21  16   0  16
 23   5  11   8  16   0

路徑示例:
A -> B -> D -> F
B -> D -> E


關鍵細節與優化要點

路徑矩陣初始化：path[i][j] = j表示直連邊下一跳為終點，這是路徑重構的基礎
負權環檢測：算法結束後若D[i][i] < 0則存在負權環
空間優化：可用一維數組滾動更新，但需保留k-1輪結果，實際節省有限
並行化潛力：最內層循環無數據依賴，適合SIMD/多線程並行


與Dijkstra算法對比

特性
Floyd-Warshall
Dijkstra(單源)
問題類型
全源最短路徑
單源最短路徑
時間複雜度
O(V³)
O(E log V) / O(V²)
適用圖類型
稠密圖、需所有點對
稀疏圖、單源查詢
負權邊支持
支持(無負權環)
不支持
路徑重構
簡單(下一跳矩陣)
需前驅數組


實際應用場景

交通網絡路由規劃(全城任意兩點導航預計算)
社交網絡六度人脈分析(全圖最短鏈路)
編譯器優化中的數據流分析(基本塊間距離)
遊戲地圖寻路預計算(小地圖全點對)


常見錯誤避坑

循環順序錯誤：k必須在最外層，i/j順序可交換
INF溢出：INF + INF可能溢出，判斷前檢查D[i][k] != INF && D[k][j] != INF
路徑矩陣更新邏輯：path[i][j] = path[i][k]而非path[k][j]
自環初始化：D[i][i] = 0必須在初始化階段設置


Floyd-Warshall算法以其簡潔的三層循環解決了全源最短路徑問題，是動態規劃在圖論中最經典的應用之一。掌握其路徑重構機制，對理解路由協議、網絡分析等領域的核心算法大有裨益。