校園導航這個課題浑槽，分別可以使用了Dijkstra(迪杰斯特拉)算法蒋失，F(xiàn)loyd（弗洛伊德）算法和Bellman-Ford算法。這三種算法都是為了解決求兩點之間最短路徑的問題桐玻。

接下來給大家分享我們理解的這三種算法。

一. Dijkstra（迪杰斯特拉）算法

?? 有人把他規(guī)劃在貪心模式算法中嫉髓，也有人把他劃在動態(tài)規(guī)劃算法中，但我覺得說法各有千秋算行。

Dijkstra算法按路徑長度遞增次序產(chǎn)生最短路徑苫耸，首先假設V是所有路徑頂點的集合，再引入兩個集合褪子，分別是

S：已求出最短路徑的頂點的集合

T=V-S：尚未確定最短路徑的頂點的集合

將T中頂點按最短路徑遞增的次序加入到S中，依據(jù)：可以證明V0到T中頂點Vk的最短路徑呀枢，或是從V0到Vk的直接路徑的權(quán)值或是從V0經(jīng)S中頂點到Vk的路徑權(quán)值之和笼痛。聽不懂吧，接下來我們來舉個例子缨伊。

我們要用一個二維數(shù)組來記錄各個頂點之間邊的關系刻坊，我們把不能直接到達的兩點之間的距離用∞（一個很大很大的數(shù)）來表示

首先要先確定一個點，我們暫且叫它源點徐块，我們接下來求的也是源點到其它各個點的最短路徑灾而，在這里我們把1號點設為源點。然后我們還需要一個一維數(shù)組dis記錄當前情況下源點到其他各個點的最短距離绰疤，并不是真的最短距離，我們把它叫做最短距離的“估計值”

拋去1號點到1號點的距離是0外（因為我們可以確定）癣猾，讓我們選出當前情況下距離1號點最近的點，就是2號點纷宇。然后我們就可以把1號點到2號點的最短距離從“估計值”變?yōu)椤按_定值”，即1號頂點到2號頂點的最短路程就是當前dis[2]值上陕。為什么呢拓春？你想啊，目前離1號頂點最近的是2號頂點硼莽，并且這個圖所有的邊都是正數(shù)，那么肯定不可能通過第三個頂點中轉(zhuǎn)偏螺，使得1號頂點到2號頂點的路程進一步縮短了匆光。因為1號頂點到其它頂點的路程肯定沒有1號到2號頂點短。

然后我們就來看看剛被我們確定的2號點能直接到哪幾個點吧终息，可以看出能直接到3號點和4號點。先討論通過2->3這條邊能否讓1號頂點到3號頂點的路程變短劲够。也就是說現(xiàn)在來比較dis[3]和dis[2]+e[2][3]的大小休傍。其中dis[3]表示1號頂點到3號頂點的路程蹲姐。dis[2]+e[2][3]中dis[2]表示1號頂點到2號頂點的路程，e[2][3]表示2->3這條邊柴墩。所以dis[2]+e[2][3]就表示從1號頂點先到2號頂點，再通過2->3這條邊逢净，到達3號頂點的路程。我們發(fā)現(xiàn)dis[3]=12爹土，dis[2]+e[2][3]=1+9=10，dis[3]>dis[2]+e[2][3]胀茵，因此dis[3]要更新為10。同理我們的dis[4]也要從∞（一個很大很大的數(shù)）被更新為4峭弟。

雖然dis[3]和dis[4]都被更新了脱拼，但先別急，它們現(xiàn)在仍是“估計值”還不是“確定值”情臭。讓我們想一想現(xiàn)在被確定的點有哪些玉组？（一個是1號點）一個是2號點。這些確定的點就不用管了惯雳，讓我們在那些還是估計值的點中選出當前情況下距離1號點最近的點，

就是4號點劈猿。然后我們就可以把1號點到4號點的最短距離從“估計值”變?yōu)椤按_定值”潮孽，即1號頂點到4號頂點的最短路程就是當前dis[4]值。

然后我們再來看看剛被我們確定的4號點能直接到哪幾個點吧往史，可以看出能直接到3號點、5號點挨决、6號點订歪。同樣用剛才的方法去更新1號點（源點）到這三個點的最短距離即dis數(shù)組中的值。

雖然dis[3]盖高、dis[5]和dis[6]都被更新了慎陵，但先別急喻奥，它們現(xiàn)在仍是“估計值”還不是“確定值”。讓我們想一想現(xiàn)在被確定的點有哪些胆筒？一個是2號點诈豌、一個是4號點。這些確定的點就不用管了矫渔，讓我們在那些還是估計值的點中選出當前情況下距離1號點最近的點，

就是3號點顿痪。然后我們就可以把1號點到3號點的最短距離從“估計值”變?yōu)椤按_定值”油够，即1號頂點到3號頂點的最短路程就是當前dis[3]值。

.........

.........

直到dis數(shù)組中的值都變成確定值揩悄。

下面給大家分享一下我們的核心的代碼

核心代碼

最后鬼悠，提醒大家，Dijkstar算法不能處理負權(quán)邊焕窝，每次都找一個距源點最近的點dmin，然后將改距離定為這個點到源點的最短距離巴帮，但如果存在負權(quán)邊虐秋，那有可能先通過并不是距源點最近的一個次優(yōu)點（dmin’），再通過這個負權(quán)邊L（L<0）熟妓，使得路徑之和更小栏尚。則dmin’+L成為最短路徑，并不是dmin抬虽，這樣dijkstra就被pass掉了。

二. Floyd算法

?? 基本思想是阐污，兩點的最短路徑不外乎有兩種可能，一種是直接最短功氨，第二種是經(jīng)過若干點最短手幢。所以，我們假設dist（AB）為節(jié)點A到節(jié)點B的最短路徑的距離围来，對于每個節(jié)點K，我們檢查dist（Ak）+dist（KB）

代碼只有短短幾行：

for (intk=0; k

? for (inti=0; i

??? for (intj=0; j

????? if(dist[i][k] + dist[k][j] < dist[i][j] ) {

??????? dist[i][j] = dist[i][k] + dist[k][j];

????? }

??? }

? }

}

最后桶错，注意的是胀蛮，我們要注意循環(huán)的嵌套順序，如果把把檢查所有節(jié)點的K放在內(nèi)層醇滥，那么結(jié)果就是不正確的。因為這樣就提前把最短路徑確定下來了阅虫，當后面存在最短路徑時也不會再更新了不跟。

三．Bellman-Ford算法

Bellman-ford算法是求含負權(quán)圖的單源最短路徑算法，效率很低窝革，但代碼很容易寫。即進行不停地松弛瘪板，每次松弛把每條邊都更新一下漆诽，若n-1次松弛后還能更新锣枝，則說明圖中有負環(huán)，無法得出結(jié)果撇叁，否則就成功完成畦贸。Bellman-ford算法有一個小優(yōu)化：每次松弛先設一個flag，初值為FALSE薄坏，若有邊更新則賦值為TRUE，最終如果還是FALSE則直接成功退出觅廓。

dist 1 [u] =

Edge[v][u]

dist k [u] = min{ dist k-1 [u], min{ dist k-1 [j] + Edge[j][u] } },

j=0,1,…,n-1,j≠u

Dijkstra算法和Bellman算法思想有很大的區(qū)別：Dijkstra算法在求解過程中涵但，源點到集合S內(nèi)各頂點的最短路徑一旦求出，則之后不變了矮瘟，修改? 的僅僅是源點到T集合中各頂點的最短路徑長度。Bellman算法在求解過程中劫侧，每次循環(huán)都要修改所有頂點的dist[ ]哨啃，也就是說源點到各頂點最短路徑長度一直要到Bellman算法結(jié)束才確定下來。