提醒：本篇含有Floyd、Dijkstra及其堆優(yōu)化和優(yōu)先隊列優(yōu)化、Bellman-Ford、死了的SPFA，篇幅較長，請選取需要觀看（以上為本篇介紹順序）

注：除Floyd和Bellman-Ford外其余算法使用vector鄰接表存圖，m表示圖的邊數(shù)，n表示圖的節(jié)點數(shù)

前置定義：

• 最短路徑指在一張有權(quán)圖中，從一個節(jié)點到達另一個節(jié)點經(jīng)過的邊的權(quán)值總和最小的路徑，最常見為單源最短路徑，即求從一個給定點分別到其他所有節(jié)點的最短路徑

• 松弛操作指通過第三點減小兩點之間的距離

• 稀疏圖指m遠小于n^2或接近n的圖，稠密圖指m接近n^2的圖，一個圖的邊越多越稠密

這里先用P3371（單源最短路徑不卡SPFA版弱化版）做例題：

首先介紹最暴力?最簡潔?最好懂的：

Floyd（江湖人稱“五行算法”（核心真的只有五行（甚至四行）））

Floyd基于貪心的算法，思想是依次枚舉三個節(jié)點，看能否通過第三個節(jié)點進行松弛，而這也注定了它O(n^3)的時間復雜度和O(n^2)的空間復雜度在絕大多數(shù)場所行不通，但它的優(yōu)勢就是可以同時實現(xiàn)多源最短路徑（求任意兩節(jié)點間最短路徑）

核心代碼：

a[ i ][ j ]表示節(jié)點 i 到 j 的最短距離，根據(jù)需要輸出就行了

Floyd雖然簡單好想，但三個for循環(huán)畢竟是個問題（想不TLE都難），于是便引出了我們最常用、最泛用、最不易被卡的最短路算法：

Dijkstra（貪心萬歲?。?/span>

Dij基于貪心，每次所有點中選出一個未被選中過的點 t ，使得點 t 到起點 s 的距離最小，再通過點 t 將其他頂點松弛。

根據(jù)這樣的操作，我們可以保證每次選中的點 t 不可能再被松弛：我們令dis[ i ]為 i?到起點 s 的已知最短距離，若節(jié)點 t 已經(jīng)被選中過，說明dis[ t ]一定小于dis[ now ]（now為當前選中進行松弛操作的節(jié)點），不然?now 應該比 t 先被選中。所以一個節(jié)點被選中后，說明其dis值已經(jīng)確定，不會在進行更改。因此最多有 n-1 個節(jié)點被選中，每次尋找點 t 時時間最多為O(n)，進行松弛操作總時間為O(n+m)這樣總時間復雜度最多就是O(n^2+(n+m) )=O(n^2)，比Floyd稍好。

核心代碼：

可這種算法的時間復雜度還是有些高，O(n^2）足以被絕大多數(shù)題目卡掉，還有沒有更快的方法呢？

我們注意，松弛操作肯定是沒法優(yōu)化了，遍歷邊的時間復雜度降不下去。但上述代碼中尋找距離起點最近的點 t 時每次都需要掃過n個點，那能不能從這里下手呢？

在數(shù)據(jù)結(jié)構(gòu)中維護一個最大值……這不就是……

堆！

我們只需要把需要的節(jié)點和它的dis值存入一個堆中，然后以dis值為關(guān)鍵詞維護最小堆，需要時再彈出堆頂元素進行松弛不就行了？

我們發(fā)現(xiàn)，如果一個節(jié)點 t 可能成為被選中進行松弛操作的節(jié)點，t 的dis值一定是被更新過的（若不被更新，則其子節(jié)點 k 仍滿足dis[?k?]<=dis[ t ]+ t 與?k 之間的距離 ，只有dis[ t ]改變才可能打破這個不等關(guān)系將 k 松弛），并且這個節(jié)點的dis值也就確定了（證明很好想，這個節(jié)點 t 的dis值既然已經(jīng)是目前最小的了，若還能被其他節(jié)點 k 松弛，說明dis[ t ]>dis[ k ]+從t到k的距離，也就是說dis[ k ]<dis[ t ]，與假設(shè)相矛盾）。

因此我們只需要在每次進行松弛操作時將那些成功被松弛的節(jié)點放入堆中即可。若堆中已經(jīng)存在該節(jié)點，就將該節(jié)點在堆中的dis值更新，再進行相應的維護。

我們知道，存在n次彈出堆頂，m次插入；堆中最多存在n個元素，維護堆的時間復雜度是O(log n)，這樣一來時間就優(yōu)化成了O( (n+m) log n )=O( m log n )。

核心代碼：

哪有什么核心代碼？手打堆所有代碼都是核心！

手打堆的代碼肉眼可見的變得非常多，那有沒有時間差不多但代碼簡單的呢？

（我都這么說了那肯定有啊）

在這里，我們要隆重請出我們的STL模板：

priority_queue（優(yōu)先隊列）

優(yōu)先隊列的本質(zhì)是一個堆，優(yōu)先隊列的top就是隊列中的最大/最小值（最大堆和最小堆需要自己定義）。優(yōu)先隊列不僅能存普通的int、long long，也可以存結(jié)構(gòu)體，但在結(jié)構(gòu)體中我們需要進行重載運算符才能維護堆。

我們知道，只有dis值被更新的節(jié)點才可能被下一次選中，因此我們需要在每次更新 t 的dis值時將 t 和dis一起放入優(yōu)先隊列中。但注意：同一節(jié)點 t 可能被更新過多次dis值，因此優(yōu)先隊列中可能存在多個 t 與其dis值，而這些無用的數(shù)據(jù)只能保留在優(yōu)先隊列中，因此優(yōu)先隊列中的元素個數(shù)最多為m個，這樣維護優(yōu)先隊列的時間就降低到了O（log m），其他的時間復雜度相同，總時間復雜度為O（m log m），比堆優(yōu)化略差

但它簡單啊

核心代碼：

至此，Dijkstra及其優(yōu)化看似很完美了實際上也很完美了，但它有一個致命的缺點：

不能解決帶有負權(quán)邊的問題

舉個圖例就知道了：

在這個圖中，我們?nèi)绻凑障惹暗乃悸罚瑧撟钕冗x中3這個節(jié)點并將其dis值確定為2，可我們?nèi)绻ㄟ^1->2->3的路徑走，會發(fā)現(xiàn)3的dis值應該為1，這就是貪心算法在解決含有負權(quán)邊時的弊端。

而下面介紹的這種算法，則解決了這種問題：

Bellman-Ford（死了一半）

這種算法的思想是每次都枚舉m條邊，看能否松弛某幾條邊。

在第一輪松弛后，我們可以得到起點最多經(jīng)過一條邊到達其余節(jié)點的最短距離；第二輪松弛后，就可以得到最多經(jīng)過兩條邊到達其余節(jié)點的最短距離。而一個節(jié)點到另一個節(jié)點的最短路徑最多需要經(jīng)過 n-1 條邊，這樣就最多需要 n-1 輪枚舉，每次枚舉 m 條邊，時間復雜度是O（nm）

核心代碼：

將上圖的負權(quán)邊代入，會發(fā)現(xiàn)3號節(jié)點的dis值最后被松弛為了1，也就是說該算法可以解決含有負權(quán)邊的問題。

但是O（nm）的時間復雜度擺在那里，在m=n^2時最壞能卡成和Floyd一樣的O（n^3），所以我們也需要用些優(yōu)（xuan）美（xue）的方法來優(yōu)化它。

我們注意，同樣，只有一個節(jié)點被松弛過，那么與它相連的節(jié)點才可能在下一輪被松弛。因此我們可以同樣使用一個隊列（注意：不需要優(yōu)先隊列，這個只是記錄順序），將該輪被松弛過的節(jié)點放入隊列中，并且隊列中不可以同時存在兩個相同的節(jié)點（同一輪只對一個節(jié)點進行一次松弛），我們可以用一個數(shù)組判重。

這種使用隊列優(yōu)化的Bellman-Ford算法，江湖人稱：

死了的SPFA（考場慎用）（但是能幫你判斷負環(huán)）

沒錯，死了的SPFA說的正是它。因為即使使用了隊列優(yōu)化，也可以輕松被普（du）通（liu）數(shù)據(jù)卡回O（nm）的原型，所以只要沒有負權(quán)邊，能用Diikstra就不要考慮SPFA的事情了。

核心代碼：

還記得么？我剛才提到了一個詞：負環(huán)。負環(huán)指的是一個邊權(quán)和小于0的環(huán)，如果一個圖存在負環(huán)，那么圖就不會存在最短路，因為每走一次負環(huán)最短路徑距離就會減少，我們可以通過這個負環(huán)進行無數(shù)次松弛。而SPFA有一個獨特的方法判斷負環(huán)：

我們已知，若不存在負環(huán)，Bellman-Ford算法最多進行?n-1?次掃描所有邊的操作，也就是一個點最多被松弛 n-1 次；在SPFA中，若一個點入隊的次數(shù)達到了n，就說明該點被松弛了n次。而理論上一個點最多只存在n-1次松弛操作，也就是說，此時圖內(nèi)含有負環(huán)，使得該節(jié)點可以一直更新dis值。我們只需要再加一個數(shù)組，存放節(jié)點入隊的次數(shù)就行了

核心代碼：

那么以上就是所有基礎(chǔ)最短路算法了，這可以說是圖中最重要的一類算法，有許多問題都可以轉(zhuǎn)化為最短路問題求解。

完結(jié)撒xck~

祈愿流浪者啊啊啊！