補完 Dijkstra 做不到的兩件事:吃得下負權邊、還能一次算出所有點對的最短路。
V-1 輪)換到「吃得下負權、還能抓負環」;Floyd-Warshall 用三層迴圈,一次算出任意兩點的最短距離。承接 Dijkstra 那頁的「最短路四選一」,這頁把負權與全點對兩塊拼齊。
1. 全部邊,鬆弛 V-1 輪 —— 不像 Dijkstra 每次挑最近的,Bellman-Ford 每一輪把每一條邊都試著鬆弛一次(dist[u] + w < dist[v] 就更新),一共跑 V-1 輪。
2. 為什麼 V-1 輪就夠? —— 任何最短路最多只會用到 V-1 條邊(再多就有重複的點=繞圈,只會更長)。每跑一輪,至少讓「多用一條邊」的最短路定型,所以 V-1 輪一定傳得到最遠的點。
3. 吃得下負權邊 —— 它不靠「挑最近的先定案」那套貪婪假設,負邊也照鬆弛,答案不會錯。這正是 Dijkstra 的死穴。
4. 順手抓負環 —— V-1 輪跑完後再多跑一輪;若竟然還能鬆弛,代表有一圈邊加起來是負的(負環),距離可以無限往下掉,最短路根本不存在。
O((V+E) log V));一旦有負權邊,Dijkstra 會算錯,得換 Bellman-Ford(慢但通吃,O(V·E))。不挑起點,一次全算 —— Dijkstra 跟 Bellman-Ford 都是「單一起點到各點」;Floyd-Warshall 直接求任意兩點 i→j 的最短距離,交出來的是一整張距離矩陣。
核心就一句 DP —— dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]):i 到 j,要嘛不繞 k、要嘛「先到 k 再到 j」,兩條取比較短的。
中繼點 k 一個一個放開 —— 最外層迴圈跑 k = 0..V-1,意思是「允許經過的中繼點」愈開愈多。跑完某個 k,dist[i][j] 就是「只准經過前面那些點」的最短路;全部放開後,就是真正的最短。
k 一定要在最外層 —— 三層迴圈 k、i、j 的順序不能亂,k 放到內層會漏掉「經過某中繼點」的解,整張表算錯。
dist[i][i]:只要有一格變成負的,就代表 i 繞一圈能讓自己更短 = 有負環。dist 陣列(要還原路徑再加一個 prev)。O(V³) 的 Floyd-Warshall,不如跑 V 次 Dijkstra(O(V·(V+E) log V)),邊少時反而更快。稠密圖才輪到 Floyd-Warshall 划算。每一輪,每個人都把「我知道的最短距離」告訴所有鄰居。傳 V-1 輪,最遠的人也一定收到最新消息。
照一串匯率換一圈,錢反而變多 = 負環套利。Bellman-Ford 專門抓這種「愈繞愈賺」的漏洞。
Floyd-Warshall 不挑出發點,一次把「任兩個地點之間的最短距離」全印成一張對照表。
兩個情境切換看:一般負權圖看距離怎麼一輪一輪往外傳、負邊怎麼把估計壓更低;有負環看距離怎麼永遠停不下來、被第 V 輪的檢查抓包。節點圈裡是編號,上方紅字若為負就是負權邊;琥珀=這輪被更新,綠色=定案。按「下一步」。
dist[] 估計:從 Bellman-Ford 基本版、偵測負環、提早結束、還原路徑、SPFA、匯率套利,到 Floyd-Warshall 全點對、還原路徑、傳遞閉包,最後一張「最短路挑工具」對照表。
❌ 有負權邊還硬用 Dijkstra —— 貪婪的「一出隊就定案」被負邊破壞,會給你錯答案(不是慢而已)。負權要 Bellman-Ford 或 Floyd-Warshall。
❌ 沒擋 dist[u] 還是 ∞ 就拿去鬆弛 —— 對還沒碰到的點做 dist[u] + w,在 C++／整數會溢位算出假的更短路。加一個 dist[u] != INF 再鬆弛最保險。
❌ 以為「某輪沒變」就等於沒負環 —— 有負環時距離永遠在變、根本不會收斂;判負環要靠「第 V 輪還能鬆弛」,不是靠有沒有停下來。
❌ Floyd-Warshall 把 k 寫進內層迴圈 —— k(中繼點)一定要在最外層,順序寫錯會漏掉「經過某中繼點」的更短路,整張表就錯了。
把答案打到對話裡,我幫你對。