一、最小生成樹與最短路徑樹的區(qū)別

最小生成樹能夠保證整個拓?fù)鋱D的所有路徑之和最小，但不能保證任意兩點之間是最短路徑。

應(yīng)用如網(wǎng)絡(luò)部線，把所有的電腦(服務(wù)器？）都連起來用的網(wǎng)線(光纖？）最少，即用最小的代價讓全村人都能上網(wǎng)

最短路徑是從一點出發(fā)，到達(dá)目的地的路徑最小。

應(yīng)用如導(dǎo)航，兩個地方怎么走距離最短。可以存在到不了的情況。

二、最小生成樹

在圖論中，無向圖 G 的生成樹（英語：Spanning Tree）是具有 G 的全部頂點，但邊數(shù)最少的連通子圖。[1]

一個圖的生成樹可能有多個。

帶權(quán)圖的生成樹中，總權(quán)重最小的稱為最小生成樹。

它在實際中有什么應(yīng)用呢？比如說有N個城市需要建立互聯(lián)的通信網(wǎng)路，如何使得需要鋪設(shè)的通信電纜的總長度最小呢？這就需要用到最小生成樹的思想了。

求取最小生成樹的算法：

2.1 Prim算法原理：

1）以某一個點開始，尋找當(dāng)前該點可以訪問的所有的邊；
2）在已經(jīng)尋找的邊中發(fā)現(xiàn)最小邊，這個邊必須有一個點還沒有訪問過，將還沒有訪問的點加入我們的集合，記錄添加的邊；
3）尋找當(dāng)前集合可以訪問的所有邊，重復(fù)2的過程，直到?jīng)]有新的點可以加入；
4）此時由所有邊構(gòu)成的樹即為最小生成樹。

參考鏈接：https://wiki.jikexueyuan.com/project/step-by-step-learning-algorithm/prim-algorithm1.html

2.2 Kruskal算法原理：

現(xiàn)在我們假設(shè)一個圖有m個節(jié)點，n條邊。首先，我們需要把m個節(jié)點看成m個獨立的生成樹，并且把n條邊按照從小到大的數(shù)據(jù)進(jìn)行排列。在n條邊中，我們依次取出其中的每一條邊，如果發(fā)現(xiàn)邊的兩個節(jié)點分別位于兩棵樹上，那么把兩棵樹合并成為一顆樹；如果樹的兩個節(jié)點位于同一棵樹上，那么忽略這條邊，繼續(xù)運行。等到所有的邊都遍歷結(jié)束之后，如果所有的生成樹可以合并成一條生成樹，那么它就是我們需要尋找的最小生成樹，反之則沒有最小生成樹。

參考鏈接：https://wiki.jikexueyuan.com/project/step-by-step-learning-algorithm/kruskal-algorithm.html

2.3 兩算法對比

總的來說，Prim算法是以點為對象，挑選與點相連的最短邊來構(gòu)成最小生成樹。而Kruskal算法是以邊為對象，不斷地加入新的不構(gòu)成環(huán)路的最短邊來構(gòu)成最小生成樹。

三、最短路徑樹

最短路徑就是從一個指定的頂點出發(fā)，計算從該頂點出發(fā)到其他所有頂點的最短路徑。
最短路徑樹SPT（Short Path Tree）是網(wǎng)絡(luò)的源點到所有結(jié)點的最短路徑構(gòu)成的樹。
常見的最短路徑算法有三種：dijkstra，floyd，Bellman-Ford和SPFA。

Dijkstra：適用于權(quán)值為非負(fù)的圖的單源最短路徑，用斐波那契堆的復(fù)雜度O(E+VlgV)
Floyd：每對節(jié)點之間的最短路徑，時間復(fù)雜度O(V^3)
BellmanFord：適用于權(quán)值有負(fù)值的圖的單源最短路徑，并且能夠檢測負(fù)圈，復(fù)雜度O(VE)
SPFA：適用于權(quán)值有負(fù)值，且沒有負(fù)圈的圖的單源最短路徑，論文中的復(fù)雜度O(kE)，k為每個節(jié)點進(jìn)入Queue的次數(shù)，且k一般<=2，但此處的復(fù)雜度證明是有問題的，其實SPFA的最壞情況應(yīng)該是O(VE).

如果說邊權(quán)中有負(fù)數(shù)怎么定義呢？如果有負(fù)邊，就要分兩種情況了。
第一種情況：如果從某點出發(fā)，可以到達(dá)一個權(quán)值和為負(fù)數(shù)的環(huán)，那么這個點到其它點的最短距離就是負(fù)無窮了，很明顯，如果有負(fù)環(huán)，且從某點可以到達(dá)這個負(fù)環(huán)，那么我可以無限得走這個負(fù)環(huán)，每走一次，距離就小一些，這種情況下，我們可以定義這個點到達(dá)其它點的最短距離為負(fù)無窮。
第二種情況：如果說不存在一個這樣的負(fù)環(huán)，那么就和沒有負(fù)權(quán)邊一樣了，但是還不是完全一樣，接下來我們介紹的四種算法中，有的是可以處理負(fù)權(quán)邊不能處理負(fù)環(huán)的，有的是可以處理負(fù)環(huán)的，有的是既不能處理負(fù)權(quán)邊也不能處理負(fù)環(huán)的。

3.1 Dijkstra

• 不能適用于負(fù)權(quán)圖
• 只適用于單源最短路問題
  如果權(quán)重是負(fù)數(shù)，那就直接pass這個算法，在這里原因不表。

單源最短路徑就是指只有一個出發(fā)點，到其它點的最短路徑問題。

以上圖G4為例，來對迪杰斯特拉進(jìn)行算法演示(以第4個頂點D為起點)。以下B節(jié)點中23應(yīng)為13。


即

算法流程：

• S1. 設(shè)置dis數(shù)組，dis[i]表示起點start到i的距離。
• S2. 從點集V中彈出一個dis值最小且未以該點為起點進(jìn)行松弛操作的點。
• S3. 從該點松弛與其領(lǐng)接的各個點更新dis數(shù)組，返回S2，循環(huán)進(jìn)行。
• 通過優(yōu)先隊列的操作可以優(yōu)化S2，之后詳細(xì)說明。

舉個例子。這個例子也是洛谷的單源最短路徑的模板題，請求出1到各點的最短路？

很顯然你用肉眼看，1到本身是0,1到2、3、4的最短路分別為2,4,3。那dijkstra的操作流程是什么呢？

首先我們先開一個dis數(shù)組，讓數(shù)組的值足夠大，dis[i]=0x7fffffff,從1開始出發(fā)，令dis[1]=0，發(fā)現(xiàn)與1相連的有三個點234，那我們一個個進(jìn)行松弛操作，比較if (dis[1]+w[i]<dis[i]),w表示各邊的權(quán)重，如果小于，那就讓其覆蓋本身的dis值，即dis[i]=dis[1]+w[i]，這一波更新完后，234的值分別為2,5,4。
然后，我們需要讓234全部入隊，并選取dis值最小的數(shù)即2繼續(xù)進(jìn)行松弛操作，發(fā)現(xiàn)連接的是3和4，繼續(xù)更新，這波結(jié)束，234的值分別為2,4,3。
接著，是上一輪dis值次小的點4，進(jìn)行操作，但是4沒有出的邊，所以不進(jìn)行操作。
最后就是剩下的一個3了，3和4還有一條權(quán)邊，但是4最小的dis值依舊是3。

下面我們發(fā)現(xiàn)算法到這就截止了，為什么呢，因為S2的一句話，未進(jìn)行松弛的點，早在第一輪234就已經(jīng)全部進(jìn)入過隊列并且已經(jīng)彈出過了，所以之后他們也不會再進(jìn)入隊列，我們可以設(shè)置一個bool類型的vis[i]數(shù)組代表第i個點是否被訪問過了，如果訪問過了就結(jié)束此循環(huán)，或者直接不push進(jìn)入隊列。

這就是整個dijkstra的算法。

總結(jié)：

Dijkstra算法是一種優(yōu)秀的經(jīng)典的最短路算法，在優(yōu)先隊列的優(yōu)化下，它的時間復(fù)雜度也是可接受的，它在計算機網(wǎng)絡(luò)等應(yīng)用中廣泛存在，然而它也有它的局限性，它的局限性甚至比Floyd算法都要大，Floyd算法允許有負(fù)權(quán)邊，不允許有負(fù)權(quán)環(huán)，Dijkstra算法連負(fù)權(quán)邊都不允許，因為Dijkstra的正確性基于以下假設(shè)：當(dāng)前未找到最短路的點中，距離源點最短的那個點，無法繼續(xù)被松弛，這時候他肯定是已經(jīng)松弛到最短狀態(tài)了。但是這個假設(shè)在有負(fù)權(quán)邊的時候就不成立了，舉一個經(jīng)典例子：一個具有三個點三條邊的圖，0->1距離為2,0->2距離為3，2->1距離為-2，根據(jù)Dijkstra算法，我們第一次肯定會將節(jié)點1加入到已經(jīng)松弛好的點集中，但是這時候是不對的，2并不是0->1最短的路徑，而通過點2松弛過的路徑：0->2->1才是最短的路徑，因為負(fù)權(quán)邊的存在，我們認(rèn)為的已經(jīng)被松弛好的點，在未來還有被松弛的可能。這個就是Dijkstra的局限性，然而這并不影響它的偉大，因為在實際應(yīng)用中，沒有負(fù)權(quán)的圖是更為常見的。但是我們?nèi)匀恍枰梢蕴幚碡?fù)權(quán)，甚至負(fù)環(huán)的算法，這時候Bellman-Ford算法和SPFA算法就派上用場了。

3.2 Floyd

弗洛伊德算法是一種基于動態(tài)規(guī)劃的多源最短路算法。是解決任意兩點間的最短路徑的一種算法，可以正確處理有向圖或有向圖或負(fù)權(quán)（但不可存在負(fù)權(quán)回路)的最短路徑問題，同時也被用于計算有向圖的傳遞閉包。

算法流程：

通過Floyd計算圖G=(V,E)中各個頂點的最短路徑時，需要引入兩個矩陣，矩陣S中的元素a[i][j]表示頂點i(第i個頂點)到頂點j(第j個頂點)的距離。矩陣P中的元素b[i][j]，表示頂點i到頂點j經(jīng)過了b[i][j]記錄的值所表示的頂點。
算法描述：
a. 從任意一條單邊路徑開始。所有兩點之間的距離是邊的權(quán)，如果兩點之間沒有邊相連，則權(quán)為無窮大。
b. 對于每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。

假設(shè)圖G中頂點個數(shù)為N，則需要對矩陣D和矩陣P進(jìn)行N次更新。初始時，矩陣D中頂點a[i][j]的距離為頂點i到頂點j的權(quán)值；如果i和j不相鄰，則a[i][j]=∞，矩陣P的值為頂點b[i][j]的j的值。 接下來開始，對矩陣D進(jìn)行N次更新。第1次更新時，如果”a[i][j]的距離” > “a[i][0]+a[0][j]”(a[i][0]+a[0][j]表示”i與j之間經(jīng)過第1個頂點的距離”)，則更新a[i][j]為”a[i][0]+a[0][j]”,更新b[i][j]=b[i][0]。 同理，第k次更新時，如果”a[i][j]的距離” > “a[i][k-1]+a[k-1][j]”，則更新a[i][j]為”a[i][k-1]+a[k-1][j]”,b[i][j]=b[i][k-1]。更新N次之后，操作完成！
舉個例子

第一步，我們先初始化兩個矩陣，得到下圖兩個矩陣：


第二步，以v1為中介，更新兩個矩陣：
發(fā)現(xiàn)，a[1][0]+a[0][6] < a[1][6] 和a[6][0]+a[0][1] < a[6][1]，所以我們只需要矩陣D和矩陣P，結(jié)果如下：


通過矩陣P，我發(fā)現(xiàn)v2–v7的最短路徑是：v2–v1–v7

第三步：以v2作為中介，來更新我們的兩個矩陣，使用同樣的原理，掃描整個矩陣，得到如下圖的結(jié)果：


OK，到這里我們也就應(yīng)該明白Floyd算法是如何工作的了，他每次都會選擇一個中介點，然后，遍歷整個矩陣，查找需要更新的值，下面還剩下五步，就不繼續(xù)演示下去了，理解了方法，我們就可以寫代碼了。

總結(jié)

Floyd算法只能在不存在負(fù)權(quán)環(huán)的情況下使用，因為其并不能判斷負(fù)權(quán)環(huán)，上面也說過，如果有負(fù)權(quán)環(huán)，那么最短路將無意義，因為我們可以不斷走負(fù)權(quán)環(huán)，這樣最短路徑值便成為了負(fù)無窮。
但是其可以處理帶負(fù)權(quán)邊但是無負(fù)權(quán)環(huán)的情況。
以上就是求多源最短路的Floyd算法，基于動態(tài)規(guī)劃，十分優(yōu)雅。
但是其復(fù)雜度確實是不敢恭維，因為要維護(hù)一個路徑矩陣，因此空間復(fù)雜度達(dá)到了O(n^ 2 ) ，時間復(fù)雜度達(dá)到了O(n^ 3)，只有在數(shù)據(jù)規(guī)模很小的時候，才適合使用這個算法。

3.3 Bellman-Ford

Bellman-Ford是最常規(guī)下的單源最短路問題，對邊的情況沒有要求，不僅可以處理負(fù)權(quán)邊，還能處理負(fù)環(huán)。可謂是來者不拒。

算法描述：

對于一個圖G(v,e)(v代表點集，e代表邊集)，執(zhí)行|v|-1次邊集的松弛操作，所謂松弛操作，就是對于每個邊e1(v,w)，將源點到w的距離更新為：原來源點到w的距離 和 源點到v的距離加上v到w的距離 中較小的那個。v-1輪松弛操作之后，判斷是否有源點能到達(dá)的負(fù)環(huán)，判斷的方法就是，再執(zhí)行一次邊集的松弛操作，如果這一輪松弛操作，有松弛成功的邊，那么就說明圖中有負(fù)環(huán)。算法復(fù)雜度為O(ne)，e為圖的邊數(shù)

優(yōu)化(SPFA)

Bellman-Ford算法雖然可以處理負(fù)環(huán)，但是時間復(fù)雜度為O(ne)，在圖為稠密圖的時候，是不可接受的。復(fù)雜度太高。我們分析一下能不能進(jìn)行優(yōu)化，Bellman-Ford算法的正確性保證依賴于路徑松弛性質(zhì)，我們只要能夠保證最短路徑中的邊的松弛順序即可，Bellman-Ford算法屬于一種暴力的算法，即，每次將所有的邊都松弛一遍，這樣肯定能保證順序，但是仔細(xì)分析不難發(fā)現(xiàn)，源點s到達(dá)其他的點的最短路徑中的第一條邊，必定是源點s與s的鄰接點相連的邊，因此，第一次松弛，我們只需要將這些邊松弛一下即可。第二條邊必定是第一次松弛的時候的鄰接點與這些鄰接點的鄰接點相連的邊（這句話是SPFA算法的關(guān)鍵，請讀者自行體會），因此我們可以這樣進(jìn)行優(yōu)化：設(shè)置一個隊列，初始的時候?qū)⒃袋cs放入，然后s出隊，松弛s與其鄰接點相連的邊，將松弛成功的點放入隊列中，然后再次取出隊列中的點，松弛該點與該點的鄰接點相連的邊，如果松弛成功，看這個鄰接點是否在隊列中，沒有則進(jìn)入，有則不管，這里要說明一下，如果發(fā)現(xiàn)某點u的鄰接點v已經(jīng)在隊列中，那么將點v再次放到隊列中是沒有意義的。因為即時你不放入隊列中，點v的鄰接點相連的邊也會被松弛，只有松弛成功的邊相連的鄰接點，且這個點沒有在隊列中，這時候稍后對其進(jìn)行松弛才有意義。因為該點已經(jīng)更新，需要重新松弛。

總結(jié)：

Bellman-Ford算法和SPFA算法，都是基于松弛操作，以及路徑松弛性質(zhì)的，不同之處在于，前者是一種很暴力的算法，為了保證順序，每次把所有的邊都松弛一遍，復(fù)雜度很高，而后者SPFA，則是在Bellman-Ford算法的基礎(chǔ)上進(jìn)行了剪枝優(yōu)化，只松弛那些可能是下一條路徑的邊，但是關(guān)于SPFA算法的復(fù)雜度，現(xiàn)在還沒有個定論，不過達(dá)成的共識是：算法的時間復(fù)雜度為O(me)，其中m為入隊的平均次數(shù)，其發(fā)明者，西安交大的段凡丁大神的論文中，m是一個常數(shù)（這個結(jié)論是錯的），我們“姑且”認(rèn)為該算法的時間復(fù)雜度為O(e)【滑稽】，的確該算法的效率是很高的，博主在oi中經(jīng)常使用這個算法，除非題目數(shù)據(jù)特意卡SPFA。或者的確是稠密圖，一般情況下不會超時。關(guān)于其判斷負(fù)環(huán)，我們可以認(rèn)為，在某個節(jié)點入隊次數(shù)達(dá)到n的時候，就可以說明遇到了負(fù)環(huán)。SPFA有兩個優(yōu)化策略：SLF：Small Label First 策略，設(shè)要加入隊列的節(jié)點是j，隊首元素為i，若d[j]<dist[i]，則將j插入隊首，否則插入隊尾； LLL：Large Label Last 策略，設(shè)隊首元素為i，隊列中所有d值的平均值為x，若d[i]>x則將i插入到隊尾，查找下一元素，直到找到某一i使d[i]<=x，則將i出隊進(jìn)行松弛操作。其實，實際應(yīng)用中，SPFA的時間復(fù)雜度是很不穩(wěn)定的，因此我們能用Dijkstra+優(yōu)先隊列，就用Dijkstra+優(yōu)先隊列為好。

https://zhuanlan.zhihu.com/p/34922624
https://zhuanlan.zhihu.com/p/150434472
https://zhuanlan.zhihu.com/p/33162490
https://zhuanlan.zhihu.com/p/40338107

總結(jié)

以上是生活随笔為你收集整理的最小生成树、最短路径树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。