- 【用途】用來解決「有向圖」中，任意兩點間的最短路徑。可以正確處理有「負權」的邊。
- 【原理】枚舉 + 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];
}
}
}
}