1. Dijstra是基于貪心思想地算法，具體做法是從源點(diǎn)開始，每次找出還沒有被最短路點(diǎn)集收錄且離源點(diǎn)最近的點(diǎn)然后對其相鄰的點(diǎn)進(jìn)行松弛，進(jìn)行n次迭代以后即可得到最短路。具體實(shí)現(xiàn)為：

????????int Dijstra(?int n?){

????????? ? memset(?dist?,?0x3f?,?sizeof?(?dist?) ) ;

????????? ? dist?[S] = 0;

????????? ? for(?int i?=?0?;?i?<?n?;?i++?) {

????????? ? ? ? int t = -1;

????????? ? ? ? for(?int i=1?;?i?<=?n?;?i++?) if?(?!?st[i] && (?t?== -1 || dist[i]?<?dist[t] ) )? t = i;

????????? ? ? ? st?[?t?] = true;

????????? ? ? ? for?(?int j?=?1?;?j?<=?n?;?j++) {

????????? ? ? ? ? ? dist?[?j?]?= min?(?dist?[?j?] ,dist?[?t?]?+?g?[?t?] [?j?] );

????????? ? ? ? }

????????? ? }

????????? ? if?(?dist[n] ==?0x3f3f3f3f?) return -1;

????????? ? return dist[n];

????????}

其中 S 為源點(diǎn)，dist [ i ]?表示源點(diǎn)到 i 號點(diǎn)的最短距離，初始化 dist [S] = 0，其他距離為正無窮，st [ i ]表示 i 號點(diǎn)是否被最短路集合收錄。

Dijstra也有堆優(yōu)化的方法，即把松弛操作用優(yōu)先隊(duì)列隊(duì)列優(yōu)化,即：

????????1. dist的源點(diǎn)的距離初始化為零，其他點(diǎn)初始化成無窮大。

????????2. 將一號點(diǎn)放入堆中。

????????3. 不斷循環(huán)，直到堆空。每一次循環(huán)中執(zhí)行的操作為：

????????? ? 彈出堆頂（與樸素版diijkstra找到S外距離最短的點(diǎn)相同，并標(biāo)記該點(diǎn)的最短路徑已確定）。用該點(diǎn)更新臨界點(diǎn)的距離，若更新成功就加入到堆中。

? 具體實(shí)現(xiàn)略，這個(gè)很好寫。

2. SPFA，號稱最短路最快算法 ( Shortest Path Fastest Algorithm ) ,是Bellman_Ford算法的隊(duì)列優(yōu)化，因此先看Bellman_Ford算法。它的思想非常暴力：進(jìn)行 n 次迭代，每次遍歷所有的邊并對該邊的終點(diǎn)進(jìn)行松弛操作，最后得到最短路。即：

????????for n次

????????????for 所有邊 a,b,w (松弛操作)

????????????????dist [b] = min ( dist [b] , back [a] + w )

這里要注意的是 back 數(shù)組，它是上一次迭代后 dist 數(shù)組的備份。這是因?yàn)樵撍惴ㄗ钔鈱拥趉次迭代的意義是：從源點(diǎn)經(jīng)過不超過k條邊的最短路。如果直接使用 dist 數(shù)組進(jìn)行松弛可能會(huì)出現(xiàn)邊的串聯(lián)現(xiàn)象。

不難看出 Bellman_Ford 的弊端：每次都要遍歷所有的邊，但不是每條邊都需要松弛。對于這一步操作進(jìn)行隊(duì)列優(yōu)化就是SPFA。即：

????????while queue 不為空

?????????????(1) t <– 隊(duì)頭

?????????????????queue.pop()

?????????????(2)用 t 更新所有出邊 t –> b，權(quán)值為w

?????????????????queue <– b (若該點(diǎn)被更新過，則拿該點(diǎn)更新其他點(diǎn))

具體實(shí)現(xiàn)為：

????????bool SPFA() {

????????? ? memset(?dist?,?0x3f?,?sizeof(dist) );

????????? ? dist?[1] = 0;

????????? ? queue?< int >? qe;

????????? ? qe.push?(1);

????????? ? st?[1] = true;//注意這里的 st 代表是否在隊(duì)列中

????????? ? while(?!?qe.empty() ) {?

????????? ? ? ? int t = qe.front();

????????? ? ? ? qe.pop();

????????? ? ? ? st?[?t?]??= false;

????????? ? ? ? for(?int i?=?h[?t?] ;?i?!= -1?;?i?=?ne?[?i?] ) {

????????? ? ? ? ? ? int j = e?[?i?] ,v = w?[?i?] ;

????????? ? ? ? ? ? if?(?dist?[?j?]?>?dist?[?t?]?+?v?){

????????? ? ? ? ? ? ? ? dist?[?j?]? = dist?[?t?]?+?v?;

????????? ? ? ? ? ? ? ? if?(?!?st?[?j?] ) {? // 以免重復(fù)加入節(jié)點(diǎn)

????????? ? ? ? ? ? ? ? ? ? st?[?j?] = true;

????????? ? ? ? ? ? ? ? ? ? qe.push(j);

????????? ? ? ? ? ? ? ? }

????????? ? ? ? ? ? }

????????? ? ? ? }

????????? ? }

????????? ? if?(?dist?[?n?]?>?0x3f3f3f3f?/?2?) return false;

????????? ? return true;

????????}

3. Floyd用于求多源最短路問題，是基于動(dòng)態(tài)規(guī)劃的算法。先用f [ i , j, k ] 表示從i走到j(luò)的路徑上除 i 和 j 點(diǎn)外只經(jīng)過1到 k 的點(diǎn)的所有路徑的最短距離，則其狀態(tài)轉(zhuǎn)移方程為：

????????????????????????f [ i , j, k ] = min ( f [ i ,? j ,?k - 1] , f [ i , k , k - 1 ] + f [ k ,? j , k - 1 ] )

由此公式可得f [ k ] [ i ] [ k ] = f [ k-1 ] [ i ] [ k ] 、f [ k ] [ k ] [ j ]? = f [ k-1 ] [ k ] [ j ] ，因?yàn)閗不可能是（i, k）或者（k, j）的中間節(jié)點(diǎn)

所以 f [ k ] [ i ]?[ j ] = min ( f [ k?1 ] [ i ] [ j ], f [ k ] [ i ] [ k ] + f [ k ] [ k ] [ j ] )

所以去掉最外層循環(huán)，因此第三層狀態(tài)可以壓縮：

????????????????????????f?[?i ,?j?]?= min?(?f?[?i?,??j?]?,?f?[?i ,?k?]?+?f [?k?,??j ] ）

具體實(shí)現(xiàn)：

????????void floyd() {

????????? ? for?(?int k?=?1?;?k?<=?n?;?k++?)

????????? ? ? ? for?(?int i?=?1?;?i?<=?n?;?i++?)

????????? ? ? ? ? ? for?(?int?j?=?1?;?j?<=?n?;?j++)

????????? ? ? ? ? ? ? ? dist?[?i?] [?j?] = min?(?dist?[?i?] [?j?] ,?dist?[?i?] [?k?]?+?dist?[?k?] [?j?] ) ;

????????}?

dist 初始化為圖的鄰接矩陣 g。

總結(jié)一下，關(guān)于算法復(fù)雜度(n為點(diǎn)數(shù)，m為邊數(shù))：

? ? Dijstra要求所有權(quán)邊都是正數(shù): ? ?

? ? ? ? Dijstra : O(n^2) ? ?適用于稠密圖

? ? ? ? 堆優(yōu)化Dijstra : O(m*logn) ?適用于稀疏圖

? ?如果存在負(fù)權(quán)邊則用SPFA: ? ?

? ? ? ? Bellman_Ford : O(n*m) ? 有邊數(shù)限制時(shí)最短路的唯一算法

? ? ? ? SPFA : 一般為?O(m)，最壞情況下為 O(n*m)，與樸素 Bellman_Ford 一樣。

????????SPFA正負(fù)權(quán)圖都可以用，并且正權(quán)圖一般情況下都快于Dijstra，但鑒于現(xiàn)在正權(quán)圖上隨手卡SPFA已是業(yè)界常識（比如網(wǎng)格圖加菊花鏈），Dijstra還是更穩(wěn)的。關(guān)于SPFA，它死了。。。。

? ? 多源匯最短路: ? ?

? ? ? ? Floyd : O(n^3) 多源最短路