中北大學(xué)ACM-ICPC課程《最短路》

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

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

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

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

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

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

what？

什么是dfs，bfs？

不會的的同學(xué)請自行腦補。

假設(shè)大家都會了，我們繼

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

應(yīng)該可以想到：

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

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

這是我們想要的結(jié)果嗎？2023/2/5中北大學(xué)ACM-ICPC集訓(xùn)隊6

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

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

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

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

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

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

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

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

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

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

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

Bellman-Ford算法

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

2023/2/5中北大學(xué)ACM-ICPC集訓(xùn)隊14什么是松弛操作？

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

2023/2/5中北大學(xué)ACM-ICPC集訓(xùn)隊16

2023/2/5中北大學(xué)ACM-ICPC集訓(xùn)隊17

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

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

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

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

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

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

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

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

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

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

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

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

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

2023/2/5中北大學(xué)ACM-ICPC集訓(xùn)隊29堆

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

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

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

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

如果圖中存在負權(quán)回路，還能不能求最短路？

那能不能判斷出來呢？Bellman-FordorSPFA2023/2/5中北大學(xué)ACM-ICPC集訓(xùn)隊32

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

Floyd算法代碼如下（w最初是圖的鄰接矩陣，算法結(jié)束后是任意點對間的最短路徑長度）：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中北大學(xué)ACM-ICPC集訓(xùn)隊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(luò)的最短路徑中經(jīng)過的編號最大的點，由此可以還原出任意點對間的具體的最短路。

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

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