最短路徑問題12-計算機科學與技術武寬wukuan_youngboy@2023/2/5中北大學ACM-ICPC集訓隊1什么是最短路徑問題？

在圖中的某一頂點（源點）到達另一個頂點（終點）的路徑權值代價最小的一條路徑。這條路徑稱之為最短路徑（ShortPath）。

給定一個圖G(V,E)，V是頂點集合，E是邊集合，每一條邊有一個權值c，給定一個起始點S和終止點D，求從S出發(fā)走到D的權值最小路徑，即為最短路徑先回憶一下：WhatisGraph？WhatisPath？2023/2/5中北大學ACM-ICPC集訓隊2圖的存儲2023/2/5中北大學ACM-ICPC集訓隊3

那么，面對最短路徑這個問題，你又什么好的想法？可以大膽的說出來。

用前幾次課的知識是否能解決？

思考一下2023/2/5中北大學ACM-ICPC集訓隊4還有沒有人記得DFS，BFS？

what？

什么是dfs，bfs？

不會的的同學請自行腦補。

假設大家都會了，我們繼

續(xù)~2023/2/5中北大學ACM-ICPC集訓隊5

應該可以想到：

DFS（深度優(yōu)先搜索）得到的結果是圖上的一條路徑，是任意的。

BFS（廣度優(yōu)先搜索）可以得到圖的最短路徑，但前提是所有路徑的權值相同。

這是我們想要的結果嗎？2023/2/5中北大學ACM-ICPC集訓隊6

顯然，我們的要求要更高一點。

但dfs與bfs確實是對圖進行所有遍歷的一個很好的方法，不會的同學希望下去可以下點功夫。

然后我們引入今天的正題，即對于一個常規(guī)的圖如何求出我們想要的最短路徑。2023/2/5中北大學ACM-ICPC集訓隊7ShortPath算法具體的形式包括：

確定起點的最短路徑問題：即已知起始結點，求最短路徑的問題。

確定終點的最短路徑問題：與確定起點的問題相反，該問題是已知終結結點，求最短路徑的問題。在無向圖中該問題與確定起點的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉的確定起點的問題。

確定起點終點的最短路徑問題：即已知起點和終點，求兩結點之間的最短路徑。

全局最短路徑問題：求圖中所有的最短路徑。2023/2/5中北大學ACM-ICPC集訓隊8

單源路徑的最短路問題：給定一個有n個點的帶權有向圖，問從指定的起點開始，到其他所有點的最短路徑。

1，不斷利用松弛操作的Bellman-Ford算法2，利用貪婪技術的Dijkstra算法

3，基于Bellman-Ford優(yōu)化的SPFA算法

4，Dijkstra的堆優(yōu)化算法2023/2/5中北大學ACM-ICPC集訓隊9單源最短路徑問題1265341284533111034單源最短路徑問題帶權圖中一個點到另一個點的最短路徑一定唯一存在？有路徑通達且沒有“負權回路”則一定存在不一定唯一單源最短路徑是否一定能構成一棵樹？如果源點到其他所有點的最短路徑都存在，則一定能找到一棵以指定的起點為根的樹（邊的方向總是從父親指向兒子）2023/2/5中北大學ACM-ICPC集訓隊11單源最短路徑問題12653412845-33111034

Bellman-Ford算法

如果邊權可以為負值，那么可以使用Bellman-Ford算法求解單源最短路徑問題。2023/2/5中北大學ACM-ICPC集訓隊13Bellman-Ford算法算法流程：初始化所有點的dist值為+∞，起點的dist值為0檢查所有邊uv，用u點的dist值與這條邊的權值之和更新v點的dist值。即對所有的邊執(zhí)行一次松弛操作。若此步驟中某個點的dist值更新了，那么可以說此步驟是“有收獲的”直到上一輪步驟2沒有收獲，或步驟2已經(jīng)重復了n輪，否則再重復一次步驟2。若最后一輪步驟2仍舊是有收獲的，那么說明起點能夠到達一個負權回路，否則目標就已經(jīng)達成了。

2023/2/5中北大學ACM-ICPC集訓隊14什么是松弛操作？

2023/2/5中北大學ACM-ICPC集訓隊15RELAX操作代碼下面看看松弛操作的一些引理

2023/2/5中北大學ACM-ICPC集訓隊16

2023/2/5中北大學ACM-ICPC集訓隊17

知道什么是松弛操作后，來看看Bellman-Ford算法吧~。2023/2/5中北大學ACM-ICPC集訓隊18Bellman-Ford算法的證明證明：如果起點能夠到達某個負權回路，那么顯然，步驟2總是會有收獲。如果起點無法到達一個負權回路，那么當所有點的dist值到達最低值時，步驟2就不再有收獲了。而一條最短路徑一定沒有環(huán)，即一條最短路徑經(jīng)過的邊數(shù)一定不會超過n-1（經(jīng)過了所有其他的點），所以n-1輪后，任何一個點作為終點的最短路徑一定已經(jīng)求得。時間復雜度顯然是O(ne)

2023/2/5中北大學ACM-ICPC集訓隊19Dijkstra算法如果邊權沒有負值，可以用Dijkstra算法求解單源最短路徑問題。

在學習算法的同時思考下為什么存在這個限制條件？2023/2/5中北大學ACM-ICPC集訓隊20Dijkstra算法算法流程：初始化所有點的dist值為+∞，起點的dist值為0從所有點中找到未被標記的dist值最小的點x，將x點標記檢查所有x引出的邊，用x點的dist值與這條邊的權值之和更新這條邊指向的點的dist值（“松弛操作”）重復步驟2和3直到所有點都被標記2023/2/5中北大學ACM-ICPC集訓隊21Dijkstra算法1265341284533111034dist:0dist:+∞dist:+∞dist:+∞dist:+∞dist:+∞dist:1dist:10dist:3dist:3dist:5dist:2dist:9

Dijkstra算法一個點的dist值就是“已知的從起點到達它的最短路徑長度”如果記下每個點的dist值最后一次更新是由哪條邊的松弛操作完成的，這條邊就是“已知的從起點到達它的最短路徑的最后一條邊”一個點被標記也就意味著“這個點的dist值已經(jīng)不可能再被更新”，即“起點到它的最短路徑已經(jīng)求得”

2023/2/5中北大學ACM-ICPC集訓隊23Dijkstra算法還記得前面說到過的迪杰斯特拉算法是基于什么思想的嘛？

貪婪技術！又稱貪心法！樸素的Dijkstra算法的時間復雜度為O(n^2)。2023/2/5中北大學ACM-ICPC集訓隊24 Bellman-Ford優(yōu)化的SPFA算法算法流程：初始化所有點的dist值為+∞，起點的dist值為0，將起點加入一個“待檢查點”的隊列q從隊列q的隊首中取出一個節(jié)點x，對x引出的所有邊執(zhí)行松弛操作，若某個點的dist值被更新了且這個點不在隊列q中，則將其加入隊尾重復步驟2直到某個點入隊超過n次或隊列為空

2023/2/5中北大學ACM-ICPC集訓隊25Bellman-Ford優(yōu)化的SPFA算法有理論能夠證明，SPFA算法的平均時間復雜度為O(e)。但是有可能退化，最壞會到O(en)。比較適合于稀疏圖中求解單源最短路徑。如果不用隊列，改用棧可以么？

2023/2/5中北大學ACM-ICPC集訓隊26Dijkstra算法的堆優(yōu)化如果所有點的dist值用一個堆來維護，“更新某個點的dist值”和“尋找dist值最小的點”就可以在O(logn)的時間復雜度內完成。總時間復雜度就變成了O(elogn)，其中e為圖中的邊數(shù)WHF！！這么多東西有木有很凌亂？那什么是堆？2023/2/5中北大學ACM-ICPC集訓隊27堆？英文名heap。知道吧？其實跟優(yōu)先隊列是一樣的道理~WTF！！什么是優(yōu)先隊列？嗯，優(yōu)先隊列嘛。很簡單英文名：priorityqueue這下都清楚了吧？2023/2/5中北大學ACM-ICPC集訓隊28

堆是一種支持高效查詢的數(shù)據(jù)結構。

堆中的某個節(jié)點的值總是不大于或不小于其父節(jié)點的值。

堆總是一顆完全樹。可將堆看做一個完全二叉樹。

優(yōu)先隊列實際上就是隊列在堆上的實現(xiàn)。

堆根據(jù)其比較關系可以分為大頂堆跟小頂堆兩種 STL中提供的priority_queue默認是大頂堆，可以通過自己重載運算符來實現(xiàn)小頂堆的優(yōu)先隊列。

2023/2/5中北大學ACM-ICPC集訓隊29堆

堆所支持的兩種操作：1，向堆中插入一個新的元素2，取出對頂元素

根據(jù)堆依建于完全二叉樹的特性，堆中的這兩種操作都可以在O(logn)的時間復雜度內完成。

有關堆的知識就提到這里，有興趣繼續(xù)了解證明的同學可以去查閱相關資料2023/2/5中北大學ACM-ICPC集訓隊30

單源最短路徑問題2023/2/5中北大學ACM-ICPC集訓隊31又一個思考

如果圖中存在負權回路，還能不能求最短路？

那能不能判斷出來呢？Bellman-FordorSPFA2023/2/5中北大學ACM-ICPC集訓隊32

任意點對最短路徑問題給定一個有n個點的帶權有向圖，問任意兩個點之間的最短路徑長度。2023/2/5中北大學ACM-ICPC集訓隊33

Floyd算法代碼如下（w最初是圖的鄰接矩陣，算法結束后是任意點對間的最短路徑長度）：fork=1tondo fori=1tondo forj=1tondo if(w[i,k]+w[k,j]<w[i,j]) w[i,j]=w[i,k]+w[k,j]2023/2/5中北大學ACM-ICPC集訓隊34fork=1tondo //此時的w[x,y]為：x到y(tǒng)的“中途只能

//經(jīng)過1..k-1這些點的”最短路徑長度

//下面的二重循環(huán)則是求“中途只能

//經(jīng)過1..k這些點的”最短路徑長度

fori=1tondo forj=1tondo if(w[i,k]+w[k,j]<w[i,j]) w[i,j]=w[i,k]+w[k,j]在w[i,j]被更新時記下其因哪個k被更新，將之存儲在mid[i,j]中，則mid[i,j]就是i到j的最短路徑中經(jīng)過的編號最大的點，由此可以還原出任意點對間的具體的最短路。

2023/2/5中北大學ACM-ICPC集訓隊35Floyd算法2023/2/5中北大學ACM-ICPC集訓隊36Floyd算法如果有負權邊但沒有負權回路，F(xiàn)loyd算法還是正確的么？答案是依然正確。但是Floyd算法沒法判斷圖中是否有負權回路存在。時間復雜度顯然是O(n^3)的。

2023/2/5中北大學ACM-ICPC集訓隊37Floyd算法如果圖中有負權回路存在，F(xiàn)loyd算法最后得到的會是什么？如果要求圖（可能是無向圖）的最小環(huán)，F(xiàn)loyd算法可以給你什么啟示么？2023/2/5中北大學ACM-ICPC集訓隊38Floyd算法如果要求次短路徑，甚至第k短路徑呢？如果這個圖存在負權回路，但要求每個點不走兩次的最短路徑呢？2023/2/5中北大學ACM-ICPC集訓隊39ClassOver謝謝大家！相應的習題課安排在下周六上午8:30地點在acm-icpc實驗室內。若時間發(fā)生變更，會在交流群，新浪微博，人人主頁掛出通知20