Dijkstra算法是貪心算法熬甫，是一個單源最短路算法胰挑，就是先記錄下從起始點到各個點的距離，然后選擇距離最小的結(jié)點椿肩，用這個最小距離加上選取的點和其他點一一比較瞻颂，看看需不需要更新起點到其他點的距離，直到所有的點選完郑象。
疑問：為什么要先選最小的點贡这？
按下圖排
如果先取小的排先是? #，10厂榛，#藕坯，30，100（把#當成是無窮大）
第二個結(jié)點的10最小噪沙，更新
得 #炼彪，10，60正歼，30辐马，100
接著是第四個結(jié)點30最小，更新
得 #局义，10喜爷，50，30萄唇，90
接著是第三個結(jié)點50最小檩帐，更新
得 #，10另萤，50湃密，30诅挑，60
最后由v5無更新，最終得#泛源，10拔妥，50，30达箍，60
如果取最大會怎么樣呢没龙？
原始序列：? #，10缎玫，#硬纤，30，100（把#當成是無窮大）
取100赃磨，無更新
取30筝家，由v4更新，得：
#煞躬，10，50逸邦，30恩沛，90
咦，我們發(fā)現(xiàn)在這一步就出現(xiàn)了問題缕减，
首先是多了50雷客，比30大，這就不符合取最大的規(guī)則了桥狡，當然這不是最重要的搅裙，你可能會說，我可以選回去麻裹芝，但是先不說這在算法上可不可以實現(xiàn)部逮，它就算可以實現(xiàn)也是復(fù)雜的。
其次嫂易，第一步取最大這個情況下后面100變小了兄朋，它因為用后面的v4更新后變成了90，這會出現(xiàn)一種什么樣的問題呢怜械？這會讓第一步的比較無效颅和，試想會不會因為v0到v5的路徑變小了，導(dǎo)致v0到某個結(jié)點的距離要大于v0到v5再到某個結(jié)點的距離呢缕允？這是有可能的峡扩，當然在這個圖里面沒有這樣的結(jié)點，但這是有可能的障本，對吧教届？
這就是錯誤的點了。
小朋友，相信這時候你又有了疑問巍佑，什么疑問呢茴迁？那便是，為什么從最大更新后原來到最大距離的那個結(jié)點的距離會變小呢萤衰？
有點饒堕义，大概知道意思就好啦。
這便是因為有別的結(jié)點和源點的距離更小啊脆栋，在加上別的結(jié)點到v5結(jié)點的距離倦卖，是不是v0到v5的距離有可能會更小，有沒有這種可能椿争，有吧怕膛？
而換了從距離最小的那個結(jié)點開始比較更新，就不會有這個問題啦秦踪。
因為你想啊褐捻，如果別的結(jié)點和源點的距離更大，在加上別的結(jié)點到v5結(jié)點的距離椅邓，是不是v0到v5的距離不可能更小柠逞，不可能，對吧景馁？這就和前面的選擇不沖突了板壮。
我想到了一個有趣的事情，如果要求當源最長路合住，大概就是這樣反過來吧绰精。
Floyd多源最短路算法
假如現(xiàn)在只允許經(jīng)過1號頂點，求任意兩點之間的最短路程透葛，應(yīng)該如何求呢笨使？只需判斷e[i][1]+e[1][j]是否比e[i][j]要小即可。e[i][j]表示的是從i號頂點到j(luò)號頂點之間的路程僚害。e[i][1]+e[1][j]表示的是從i號頂點先到1號頂點阱表，再從1號頂點到j(luò)號頂點的路程之和。其中i是1~n循環(huán)贡珊，j也是1~n循環(huán)最爬，代碼實現(xiàn)如下。
for (i = 1; i <= n; i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? for (j = 1; j <= n; j++)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? if (e[i][j] > e[i][1] + e[1][j])
? ? ? ? ? ? ? ? ? ? ? ? e[i][j] = e[i][1] + e[1][j];
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
接下來繼續(xù)求在只允許經(jīng)過1和2號兩個頂點的情況下任意兩點之間的最短路程门岔。如何做呢爱致？我們需要在只允許經(jīng)過1號頂點時任意兩點的最短路程的結(jié)果下，再判斷如果經(jīng)過2號頂點是否可以使得i號頂點到j(luò)號頂點之間的路程變得更短寒随。即判斷e[i][2]+e[2][j]是否比e[i][j]要小糠悯，代碼實現(xiàn)為如下帮坚。
//經(jīng)過1號頂點
for(i=1;i<=n;i++)?
for(j=1;j<=n;j++)?
if (e[i][j] > e[i][1]+e[1][j])? e[i][j]=e[i][1]+e[1][j];?
//經(jīng)過2號頂點
for(i=1;i<=n;i++)?
for(j=1;j<=n;j++)?
if (e[i][j] > e[i][2]+e[2][j])? e[i][j]=e[i][2]+e[2][j];
最后允許通過所有頂點作為中轉(zhuǎn)
整個算法過程雖然說起來很麻煩，但是代碼實現(xiàn)卻非常簡單互艾，核心代碼只有五行：
for(k=1;k<=n;k++)
? ? for(i=1;i<=n;i++)?
? ? for(j=1;j<=n;j++)?
? ? if(e[i][j]>e[i][k]+e[k][j])?
? ? ? ? ? ? ? ? ? ? e[i][j]=e[i][k]+e[k][j];
這段代碼的基本思想就是：最開始只允許經(jīng)過1號頂點進行中轉(zhuǎn)试和，接下來只允許經(jīng)過1和2號頂點進行中轉(zhuǎn)……允許經(jīng)過1~n號所有頂點進行中轉(zhuǎn)，求任意兩點之間的最短路程纫普。用一句話概括就是：從i號頂點到j(luò)號頂點只經(jīng)過前k號點的最短路程阅悍。
另外需要注意的是：Floyd-Warshall算法不能解決帶有“負權(quán)回路”（或者叫“負權(quán)環(huán)”）的圖，因為帶有“負權(quán)回路”的圖沒有最短路昨稼。例如下面這個圖就不存在1號頂點到3號頂點的最短路徑节视。因為1->2->3->1->2->3->…->1->2->3這樣路徑中，每繞一次1->-2>3這樣的環(huán)假栓，最短路就會減少1寻行，永遠找不到最短路。其實如果一個圖中帶有“負權(quán)回路”那么這個圖則沒有最短路匾荆。
看了這里拌蜘，首先有一個疑問：怎么這個三重循環(huán)的兩個節(jié)點之間只更新了1次？只能有兩段邊或者是一段邊的情況么牙丽？顯然不是的简卧。
為什么不是呢？我們先一個個分析剩岳，當k中轉(zhuǎn)站只有一個的時候贞滨，顯然是這樣的入热。但是當k有多個的時候就不是這樣子的了拍棕。
為啥不是呢？我看著這個循環(huán)就像只更了一次啊勺良。
小朋友绰播，那你有木有注意到它里面也是有兩個循環(huán)滴，好像不好理解喔尚困。
更新就更新蠢箩，你用兩個循環(huán)是啥意思呢？
這就是問題的切入點了事甜。
這我們只能從每一個循環(huán)開始看谬泌，假如只允許一個結(jié)點進行中轉(zhuǎn)，e[i][j]表示的是從i號頂點到j(luò)號頂點之間的路程逻谦。e[i][1]+e[1][j]表示的是從i號頂點先到1號頂點掌实，再從1號頂點到j(luò)號頂點的路程之和。而兩重循環(huán)把n個頂點之間的聯(lián)系都遍歷了一遍邦马，可以得出是否需要經(jīng)過中轉(zhuǎn)最短贱鼻。
我們可以假設(shè)有4個頂點宴卖，v1,v2,v3,v4.。
把v1看成是中轉(zhuǎn)的頂點v2到v3的最短路為2 1 3
v2到v4的最短路為2 4
如果把v3變成是可以中轉(zhuǎn)的頂點邻悬，是不是有這樣子的可能症昏，v2到v4之間的最短路可以是 2 1 3 4，有這種可能父丰，對吧肝谭？
那這在兩個兩重循環(huán)里面是怎么體現(xiàn)的呢？一個兩重循環(huán)可以理解础米，那兩個分苇，n個要怎么理解呢？
從兩個開始說起吧屁桑，我們需要理解兩個頂點之間是怎么出現(xiàn)3條邊和兩個頂點的医寿。
以我們上面說的四個結(jié)點為例子，首先蘑斧，把v1當成是中轉(zhuǎn)站靖秩，e[2][3]=e[2][1]+e[1][3]，沒問題竖瘾，對吧沟突。
進入到第二個二重循環(huán)，把v3加入作為中轉(zhuǎn)站捕传，e[2][4]=e[2][3]+e[3][4]惠拭，再把e[2][3]展開就對了。
這就是最外層循環(huán)和里面兩重循環(huán)的聯(lián)系了庸论，外面的循環(huán)將里面的兩重循環(huán)后的值發(fā)生了變化职辅，一直變化著，一步步迭代更新聂示。
小朋友域携，你好像又有了新的疑問，那個鱼喉，為什么單源最短路需要從和源點距離最短的的結(jié)點開始選擇秀鞭，而這種算法卻不用把中轉(zhuǎn)結(jié)點也這樣子選更新的結(jié)點呢？
哎扛禽，其實是不一樣的锋边，哪里不一樣呢？
首先编曼，你有沒有發(fā)現(xiàn)豆巨，Dijkstra算法里面的v0（源點）并不是中轉(zhuǎn)點，Dijkstra算法的中轉(zhuǎn)點是從和源點距離最短的的結(jié)點開始遞增地一個個選擇的灵巧，這就讓它的中轉(zhuǎn)點不能亂選搀矫，不然可能前面的選擇就無效了（前面已經(jīng)分析過了）抹沪。
而為什么Floyd算法就可以亂選呢？首先它的中轉(zhuǎn)點是確定的瓤球，再隨意選擇源點和終點融欧，當也不是隨意的，因為最后它都會把所有的源點和終點通過兩重循環(huán)選完卦羡。
而它們兩兩之間在每個二重循環(huán)里面是不沖突的噪馏，因為只有一個中轉(zhuǎn)點。
如果加入了中轉(zhuǎn)點绿饵，它也是不沖突的欠肾，它一遍遍地更新了最短路。
你可能會想拟赊，你前面舉的例子的終點改變了（把3改成了4）刺桃，那如果不變呢？
好吸祟，我們來看不變的情況瑟慈。我們用v3作為第一個中轉(zhuǎn)的結(jié)點
e[2][7]=e[2][3]+e[3][7]假設(shè)更新了，經(jīng)過v3是2到7的最短路屋匕。
再加上v4作為中轉(zhuǎn)葛碧，我們發(fā)現(xiàn)它也是不沖突的。
我們可以對e[3][7]進行更新过吻，也可以對e[2][7]=e[2][4]+e[4][7]進行更新进泼。
哇，你可能會想纤虽，哇乳绕，它變了，可能沖突了哇廓推。
可系刷袍，真的嗎翩隧？
反正怪怪的樊展。
其實沒有的，先是可能e[2][7]=e[2][3]+e[3][7]堆生，然后可能更新為e[2][7]=e[2][4]+e[4][7]
沖突在哪里专缠？沒有吧，這個算法只是窮舉了所有的情況淑仆。
你可能還有一個問題涝婉，這是什么破算法，我直接用Dijkstra算法遍歷n次來不就完了嗎蔗怠？
額墩弯，問題是不一定好啊吩跋，而且想把復(fù)雜度降下來，程序?qū)懫饋磉€蠻復(fù)雜的渔工。后面有時間再想吧锌钮。
好了，吐血三升引矩，一個三個循環(huán)的算法梁丘，居然想了半天，罷遼旺韭，罷遼氛谜，還有問題也不想遼。
注意：如果兩個頂點之間沒有邊的話区端，應(yīng)該定義為正無窮值漫，后面才能慢慢變小。
Prim算法也是貪心算法來著织盼，是從頂點開始選取的惭嚣，這和kruskal算法有很大區(qū)別。
Kruskal算法悔政，將森林合并成樹晚吞。起始的每個結(jié)點它也當成是一個樹。先把所有權(quán)重的邊都選出來（因為是森林谋国，所以不能只取一邊） 槽地，不構(gòu)成回路就行，直到 ?? V-1條邊和邊集合中沒了元素芦瘾，構(gòu)成回路的邊扔掉捌蚊。
簡單說，就是不斷地把最小邊選出來近弟，并且不能構(gòu)成回路缅糟，最后選到V-1條邊就沒了，再選就一定會構(gòu)成回路祷愉。這就能將多個結(jié)點并成一棵樹了窗宦。
