信息工程大學算法設計與分析綜合應用—最短路徑問題-貝爾曼·福特算法國家級實驗教學示范中心計算機學科組規劃教材算法設計與分析Python案例詳解微課視頻版當圖中存在負權邊時，迪杰斯特拉算法無法正確求解單源最短路徑問題。這種情況下，該如何求解呢？理查德·貝爾曼（RichardBellman）和萊斯特·福特共同提出了Bellman-Ford算法。

該算法可以求解有負權邊的單源最短路徑問題，也可以判斷圖中是否存在負環。

邊(u,v)的松弛過程：Relax(u,v,w){if(d[v]>d[u]+w(u,v)){d[v]=d[u]+w(u,v);pre[v]=u;}}d[v]：記錄源點s到v的最短路徑估計w(u,v)：記錄點u到點v的邊的權值pre[v]：記錄點v的前驅uvsBellman-Ford算法通過邊的松弛操作得到單源最短路徑。Bellman-Ford算法過程：1.對所有邊進行(|V|-1)

輪松弛操作，得到源點到所有點的最短路徑長度；2.再進行1輪松弛操作，如果發現某些點的最短路徑長度仍有更新，則說明圖中存在負環。

初始化點dpreA0-1B∞-1C∞-1D∞-1E∞-11.初始化，設源點為A。初始化d數組。初始化pre數組。

初始化第一輪點dpredpreA0-10-1B∞-1-1AC∞-12BD∞-11BE∞-11B2.對所有邊進行第一輪松弛操作。依次遍歷邊A->B、E->D、B->D、D->B、B->E、A->C、B->C、D->C，修改d數組和pre數組。

初始化第一輪第二輪點dpredpredpreA0-10-10-1B∞-1-1A-1AC∞-12B2BD∞-11B-2EE∞-11B1B3.對所有邊進行第二輪松弛操作。依次遍歷邊A->B、E->D、B->D、D->B、B->E、A->C、B->C、D->C，修改d數組和pre數組。

初始化第一輪第二輪第三輪第四輪第五輪點dpredpredpredpredpredpreA0-10-10-10-10-10-1B∞-1-1A-1A-1A-1A-1AC∞-12B2B2B2B2BD∞-11B-2E-2E-2E-2EE∞-11B1B1B1B1B4.對所有邊進行第三~五輪松弛操作。依次遍歷邊A->B、E->D、B->D、D->B、B->E、A->C、B->C、D->C，修改d數組和pre數組。/*貝爾曼?福特算法求解單源最短路徑*/voidBellman-Ford(G,w,s){/*G表示有向網，w表示鄰接矩陣，s表示源點*//*1.初始化*/d[s]=0;pre[s]=-1;foreachv∈V-{s}{d[v]=+∞;pre[v]=-1;}

/*2.松弛步驟*/fori=1to|V|-1foreachedge(u,v)∈Eif(d[v]>d[u]+w(u,v)){ d[v]=d[u]+w(u,v); pre[v]=u;}

/*3.檢查是否存在負值環*/foreachedge(u,v)∈Eif(d[v]>d[u]+w(u,v)) printf(“存在負值環”);}時間復雜度：O(VE)

定理：如果圖G=(V,E)不包含負環，執行Bellman-Ford算法后，d[v]即是源點s到點v的最短路徑距離。證明：假設v是G中的任一結點，從源點s到v、且邊數最少的最短路徑為p，如圖10-10所示：

證明：假設v是G中的任一結點，從源點v0到vk、長度最短且邊數最少的最短路徑為p，如下圖所示：

由于p是最短路徑，有d[vi]=d[vi-1]+w(vi-1,vi)。

第一輪遍歷后，有d[v1]=d[v0]+w(v0,v1)；

第二輪遍歷后，有d[v2]=d[v1]+w(v1,v2)；

……

第k輪遍歷后，有d[v]=d[vk]=d[vk-1]+w(vk-1,vk)。

由于圖G沒有負值環存在，路徑p是一條簡單路徑（邊數最少），因此，路徑p最多有(|V|-1)條邊，Bellman-Ford算法經過(|V|-1)輪遍歷后，可以得到每個點的單源最短路徑。

推論：如果在(|V|-1)輪遍歷后，存在某個點的最短路徑距離仍然有變化，那么G中存在負值環。

如下圖所示，經過(|V|-1)輪遍歷，可得從源點到v1、v2、…、vk的當前最短路徑距離；

繼續進行第|V|輪遍歷時，假定從vk到v2存在一條邊，此時d[v2]=min{d[v2],d[vk]+w(vk,v2)}，若d[v2]有更新，說明從源點s(v0)->v1->v2->…->vk->v2是比s(v0)->v1->v2更短的一條路徑，即v2->…->vk->v2構成一個負值環。因此，推論成立。負環思考：什么情況發生松弛操作？只有d[u]更新后，從u發出的點才可能進行松弛操作。

初始化第一輪第二輪第三輪第四輪第五輪點dpredpredpredpredpredpreA0-10-10-10-10-10-1B∞-1-1A-1A-1A-1A-1AC∞-12B2B2B2B2BD∞-11B-2E-2E-2E-2EE∞-11B1B1B1B1BBellman-Ford算法的優化1.首先對從源點發出的邊進行松弛操作；2.找到d[u]降低的點u，繼續對從點u發出的邊進行松弛操作；3.重復步驟2，直到所有點的最短路徑長度d[i]都不再改變。SPFA(ShortestPathFasterAlgorithm)while(隊列不為空){取出隊列中結點；松弛它發出的邊；把最短路徑長度有更新的點加入隊列；}隊列d[A]d[B]d[C]d[D]d[E]A0∞∞∞∞B、C0-14∞∞C、D、E0-1211D、E0-1211E0-1211D0-12-210-12-21S