最短路徑總整理

我們在最短路徑時介紹了 Bellman-Ford 演算法和 Dijkstra's 演算法，在全點對最短路徑時介紹了 Floyd-Warshall 演算法，這些演算法究竟各自有什麼差別或優勢呢？我不能只學一個就好了嗎？

本篇文章將簡介幾個在遭遇最短路徑問題常見的狀況，來加深讀者對各個演算法的印象。

可能在讀完最短路徑時就有讀者已經想過：我幹嘛學 Bellman-Ford 演算法？Dijkstra's 演算法的時間複雜度不是嚴格好嗎？

別忘記，我們在最一開始介紹時假設了圖的邊權都是正值，那如果現在出現了負值，會發生什麼事呢？

沒錯，在以下範例，按照 Dijkstra's 演算法的做法來模擬會無法得到正確的最短路徑：

在上圖的這個例子中，假設我們用 $0$ 當作起點，Dijkstra's 演算法理論上會根據以下流程執行：

• 初始化每個人的距離成 $[0, \infty, \infty, \infty]$。
• $0$ 是目前距離最短的點，拿 $0$ 出來做鬆弛，距離此時變成 $[\color{gray}{0}, 4, 1, \infty]$。
• $2$ 是目前距離最短的點，拿 $2$ 出來做鬆弛，距離此時變成 $[\color{gray}{0}, 4, \color{gray}{1}, 3]$。
• $3$ 是目前距離最短的點，拿 $3$ 出來做鬆弛，距離此時變成 $[\color{gray}{0}, 4, \color{gray}{1}, \color{gray}{3}]$。
• $1$ 是目前距離最短的點，拿 $1$ 出來做鬆弛，距離此時變成 $[\color{gray}{0}, \color{gray}{4}, \color{gray}{1}, \color{gray}{3}]$。
  • 此時需要注意的是，因為 $3$ 已經被拿出來過了，所以 $1$ 對 $3$ 的鬆弛並不會成功！

實際上，$0$ 到 $3$ 的最短路徑應該是 $1$ 才對，但上面的演算法流程卻會得到 $3$，造成錯誤。

讀者可能會想說：那我就不要管點有沒有被拿出來過，硬是鬆弛就好啦！可惜的是，這樣問題依然還是存在的，例如只要我們在 $3$ 後面增加一個點 $4$，這樣由於 $3$ 不會再被拿出來第二次，所以 $4$ 被鬆弛到時是用舊版的 $3$ 的距離去計算的，如此一來最短距離就錯了。

更細心的讀者可能還會發現到，我們在最短路徑裡實作的 $O(M\log M)$ Dijkstra's 演算法其實並沒有真的紀錄「一個點是否被拿出來過」，而是直接偷懶的只要發現一個點有被鬆弛成功就把點加進 priority_queue 裡面。用這樣的實作方式，確實還真的可以讓有負權的圖輸出正確，那問題到底在哪呢？

問題在一個點必須被拿出來很多次！

原本 Dijkstra's 演算法的時間複雜度就是建立在每個點只需要拿出來一次而已；既然現在每個點要拿出來很多次的話，這個複雜度分析當然就不正確了。更可怕的是，在有負權圖的情況下，我們介紹的這個 Dijkstra's 演算法實作，是真的會讓一個點被拿出來指數次的！

既然這麼可怕，那我們到底要怎麼對付負權圖呢？答案是使用 Bellman-Ford 演算法！

如果回顧 Bellman-Ford 演算法的介紹，就會發現他無論是在正確性還是複雜度上的分析，都沒有用到邊權得是正值的這個條件，因此在有負權的圖上，退一步使用 $O(NM)$ 的 Bellman-Ford 演算法才是正道。唯獨一件事情需要特別注意……

要注意什麼？就是當圖中有「負環」的時候會需要做特別處理，例如以下情況：

在這張圖上，從 $0$ 走到 $2$ 的最短路徑究竟是多短呢？答案是無限短！因為路徑可以不斷地照著 $$0\to 1\to 2\to 0\to 1\to 2\to \cdots$$ 的規律延伸下去，就可以永遠的讓最短距離變短。

那如果我們在這張圖執行 Bellman-Ford 演算法的話，究竟會發生什麼事呢？回想一下 Bellman-Ford 演算法的正確性證明：因為最長的最短距離至多只能使用 $N-1$ 條邊，所以跑 $N-1$ 輪鬆弛就可以算好所有點的最短路徑。

有負環的情況其實也就是用了無限條邊。反過來想的話，如果一個路徑用了超過 $N-1$ 條邊，那他一定有重複經過一個點兩次以上，這時我們只要把這個重複經過的點的「第一次經過」和「第二次經過」中間的片段拿出來，這段片段就肯定是一個環，如果這個環的權重和是非負值，那直接把這個環弄消失也不會讓最短距離變長；但如果權重和是負值的話，就代表這是一個負環！

因此，使用 Bellman-Ford 演算法其實可以很乾脆的利用以下方法處理有負環的圖：如果一個點在鬆弛 $N-1$ 輪之後還可以被鬆弛，那這個點肯定就可以被負環走到。

• 這裡其實還有一些細節沒有講清楚，就留給讀者自行思考。

綜上所述，讀者在解題時還請務必要想過一遍題目的限制究竟有沒有負邊，有的話是否有可能有負環呢？試著考慮了這些情況後再著手寫程式，才不會掉進無窮 WA 或 TLE 的陷阱裡。

Floyd-Warshall 演算法又簡潔又好寫，但真的只要看到全點對最短路徑就可以直接搬出 Floyd-Warshall 演算法嗎？

不妨看看限制稍微不一樣的全點對最短路徑題目：如果輸入的總點數和總邊數 $N, M$ 都不超過 $3000$ 呢？

此時執行 Floyd-Warshall 演算法會需要花上 $3000^3$ 的時間，是非常容易吃下 TLE 的，但注意到有個特別的地方是邊數跟點數差不多多，這時候其實我們要的不是跑 Floyd-Warshall 演算法，而是跑 $N$ 次 Dijkstra's 演算法，也就是把每個點都當成起點跑一次，就可以在 $O(NM\log M)$ 的時間內得到全點對最短路徑了！

再進階一點，如果此時圖有負權呢？我們前面已經提到，有負權的圖是不能跑 Dijkstra's 演算法的，但如果跑 $N$ 次 Bellman-Ford 演算法，時間複雜度會退化成 $O(N^2M)$，其實幾乎是輸給了 Floyd-Warshall 演算法。

• 沒錯，Floyd-Warshall 演算法也不受負邊權的影響，至於怎麼用 Floyd-Warshall 演算法處理負環，就交給讀者做思考了。

這裡處理的方法其實非常的進階，會需要使用到 Johnson's algorithm，但由於其涉及的理論稍微超出了我們當前的範疇，用處也不算太廣，這部分我們就留到未來的篇章再做介紹吧！

如果讀者有從不同的地方學習最短路徑的話，可能會發現不少地方會把 Dijkstra's 演算法的時間複雜度寫成 $O(M\log N)$ 而不是我們一直使用的 $O(M\log M)$，這兩者的差別是什麼呢？

有趣的是，這兩者可以說是幾乎沒有差。

這是因為在一張有向圖上，有用的邊頂多只有 $N\times (N-1)$ 條而已，也就是對於每一組點對 $(u, v)$，只有一條從 $u$ 到 $v$ 的邊有用而已，倘若真的有多條，那我們只要保留最短的那條就好啦！

因此，其實我們有$$O(\log M) = O(\log (N\times (N-1))) = O(\log N^2) = O(2\log N) = O(\log N)$$所以在最短路徑的情況下，不論寫 $O(\log M)$ 或是 $O(\log N)$，基本上都是一樣的。前面為了避免混淆我們都是寫 $O(\log M)$，不過其實寫成 $O(\log N)$ 是更多人的習慣，既然讀者都讀到這裡了，我們之後就回到 $O(\log N)$ 的懷抱吧。

畢竟每個演算法都還是有它們各自的優勢，為了讓讀者一目瞭然，我們來幫大家做個總整理。

有了這些基本認識後，希望讀者能更有概念的去根據題目需求來使用對應的演算法。

本文章沒有直接對應練習的習題，但若讀者希望對這些演算法了解得更透徹，可以考慮挑戰以下兩道習題來增加自己對最短路徑演算法的熟悉度。