基本概念

圖：

有頂點和邊組成。又分為

有向圖：

在這里只能從A到B，不能從B到A。

無向圖：

能從A到B，也能從B到A，也可以用下圖表示：

還有就是給邊加上權(quán)重，變成加權(quán)圖：

權(quán)重代表了兩個頂點連接的程度，它可以是時間、距離、路費等等，根據(jù)實際情況而定。

最短路徑：

如上圖，從A到D，有三種路徑：ABD、AD、ACD。

考慮到邊的權(quán)重（比如路費），三條線路中最短路徑不是兩點直連的AD（10），而是ABD（2 3=5）。

負環(huán)路：

雖然從現(xiàn)實場景中，人們很難想象邊的權(quán)重是負數(shù)——沒聽說過走高速從A到B，不用交高速費，還倒找錢的。

但是從理論上來說，還是要考慮負權(quán)邊的存在，這就導(dǎo)致一個問題：負環(huán)路的存在導(dǎo)致無法找出最短路徑。

看下圖：

從A到A，花費的是0，這是最短路徑了，但是因為有了負權(quán)邊的存在，會造成：

A-B-C-A，權(quán)重為2 2-5=-1，也就是說A繞了一圈，變成-1，比0小，最短路徑是ABCA了。

這還沒完，再繞一圈，-1 2 2-5=-2，A變成了-2，照此循環(huán)下去，A到A的權(quán)重會越來越小。

這就是負環(huán)路，永遠找不到最短路徑。

當(dāng)然，有負權(quán)邊不代表一定有負環(huán)路，如下圖：

這就沒有形成負環(huán)路，A到C的最短路徑就是ABC=3

廣度搜索優(yōu)先：

簡單地說，就是從根節(jié)點開始，搜索完其子節(jié)點后，再搜索子節(jié)點的子節(jié)點，直至找到目標(biāo)節(jié)點或所有節(jié)點都被遍歷一遍。

如上圖，將根節(jié)點A的子節(jié)點BCD放入隊列，取出B，再將B的子節(jié)點EF放入隊列，接著取出C，再將C的子節(jié)點G放入隊列，按照隊列先進先出的特性，遍歷所有節(jié)點。

深度搜索優(yōu)先：

從根節(jié)點開始，搜索完一條分支后，再搜索另一分支。

如上圖，取根節(jié)點A壓入棧。

取出A，獲取A的子節(jié)點BCD，壓入棧。

取出B，獲取B的子節(jié)點EF，壓入棧。

取出F，并無子節(jié)點，且不是目標(biāo)節(jié)點，拋出。E同理。

取出C，獲取C的子節(jié)點G，壓入棧。

取出G，同F(xiàn)。

取出D，獲取D的子節(jié)點H，壓入棧。

取出H，同F(xiàn)。

松弛操作：

如上圖，算出A到D的最短路徑。

一開始我們只知道A到A的路徑是0，到BCD的路徑未知，就設(shè)為∞。

計算A-D路徑為0 10=10 <∞，故將D由∞改為10。這就是一次松弛操作。

貝爾曼-福特算法

簡單地說，就是對圖中所有訂單、所有邊都進行松弛操作，直到找到最短路徑。所以其時間復(fù)雜度應(yīng)該是O（頂點數(shù)*邊數(shù)）。

偽代碼應(yīng)該是：

for(int i=0;i<頂點數(shù)-1;i  ){
 for(int j=0;j<邊數(shù);j  ){
  松弛操作;
 }
}

但在實際情況中，在小于“頂點數(shù)-1”次的遍歷中，已經(jīng)求出了最短路徑，所以在內(nèi)部循環(huán)結(jié)束后，校驗一下有沒有進行松弛操作，如果沒有，則說明已求出最短路徑，直接跳出即可。

偽代碼：

for(int i=0;i<頂點數(shù)-1;i  ){
 是否進行了松弛操作=false;
 for(int j=0;j<邊數(shù);j  ){
  if(終點權(quán)重>起點權(quán)重 邊權(quán)重){
   松弛操作：終點權(quán)重=起點權(quán)重 邊權(quán)重;終點的起點設(shè)為起點名稱;
   是否進行了松弛操作=true;
  }
 }
 if(沒有進行松弛操作){
  break;
 }
}

再結(jié)合之前談到的負環(huán)路，在執(zhí)行完最多頂點數(shù)-1次循環(huán)后，理應(yīng)得到最短路徑，如果我們額外再遍歷一次所有的邊，看看有沒有進行松弛操作。如果有，說明存在負環(huán)路。

添加偽代碼：

是否存在負環(huán)路=false;
for(int j=0;j<邊數(shù);j  ){
 if(終點權(quán)重>起點權(quán)重 邊權(quán)重){
  是否存在負環(huán)路=true;
  break;  
 }
}

操作步驟：

如上圖，共有5個頂點：ABCDE。

16條邊（無向圖，每條線代表兩個邊）：AB、AC、AD、BA、BC、BE、CA、CB、CD、CE、DA、DC、DE、EB、EC、ED

以A為起點，計算到其他頂點的最短路徑。

初始狀態(tài)下，A的權(quán)重應(yīng)為0，其他節(jié)點皆為∞。

1、處理AB，B的權(quán)重改為1。此時A=0，B=1，其余為∞。B的起點為A。

2、處理AC，C的權(quán)重改為7。此時A=0，B=1，C=7。C的起點為A。

3、處理AD，D的權(quán)重改為6。此時A=0，B=1，C=7，D=6。D的起點為A。

4、處理BA，BA=1 1=2>0，無須進行松弛操作。

5、處理BC，BC=1 1=2<7，C的權(quán)重改為2，此時A=0，B=1，C=2，D=6。C的起點改為B。

6、接著繼續(xù)處理，本次對所有邊的循環(huán)，得出如下結(jié)果：

A到各點最低消耗：A=0，B=1，C=2，D=6，E=4

各點的起點：B<--A，C<--B，D<--A，E<--C。

7、接著開啟下一輪對所有邊的循環(huán)，在此次循環(huán)中，沒有進行松弛操作，故跳出循環(huán)。

8、判斷沒有負環(huán)路，至此得出最終結(jié)果。