【筆記】Floyd-Warshall algorithm 全點對最短路徑

  • 【用途】用來解決「有向圖」中,任意兩點間的最短路徑。可以正確處理有「負權」的邊。
  • 【原理】枚舉 + DP
  • 【實作】
    • 枚舉所有中間點 (i),更新所有【j –> k】的最短路徑。
    • dis[j][k] = dis[j][i] + dis[i][k]
  • 【複雜度】
    • 時間複雜度:O(N3)
    • 空間複雜度:O(N2)
  • 【範例】ZeroJudge d282: 11015 – 05-2 Rendezvous
  • 【更多練習】TIOJ 1034 . 搶救雷恩大兵 (Saving Ryan)
// 初始值:起點終點相同時設為 0,其餘設為INF
// 因為後續有加法運算,因此INF = 0x3FFFFFFF
for (int i = 0; i < maxn; i++){
    for (int j = 0; j < maxn; j++){
        if (i == j) dis[i][j] = 0;
        else dis[i][j] = 0x3FFFFFFF;
    }
}

// Floyd-Warshall做法
// i:枚舉中間點
// j, k:計算all-pairs shortest path
for (int i = 0; i < maxn; i++){
    for (int j = 0; j < maxn; j++){
        for (int k = 0; k < maxn; k++){
            if (dis[j][k] > dis[j][i] + dis[i][k]){
                dis[j][k] = dis[j][i] + dis[i][k];
            }
        }
    }
}
分享本文 Share with friends