贝尔曼-福特算法

算法

贝尔曼-福特算法与迪科斯彻算法类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。
然而，迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作；而贝尔曼-福特算法简单地对所有边进行松弛操作，共次，其中是图的点的数量。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。
贝尔曼-福特算法的最多运行（大O符号）次，和分别是节点和边的数量）。

pseudocode

procedure BellmanFord(list vertices, list edges, vertex source)
   // 讀入邊和節點的列表並對distance和predecessor寫入最短路徑// 初始化圖for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null

   // 對每一條邊重複操作for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // 檢查是否有負權重的迴圈for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "圖包含具負權重的迴圈"

松弛

每次松弛操作实际上是对相邻节点的访问，第次松弛操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过条边，所以可知贝尔曼-福特算法所得为最短路径。

负边权操作

与迪科斯彻算法不同的是，迪科斯彻算法的基本操作“拓展”是在深度上寻路，而“松弛”操作则是在广度上寻路，这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。

负权环判定

因为负权环可以无限制的降低总花费，所以如果发现第次操作仍可降低花销，就一定存在负权环。

循环的提前跳出

在实际操作中，贝尔曼-福特算法经常会在未达到次前就出解，其实是最大值。于是可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。

队列优化

西南交通大学的段凡丁于1994年提出了用队列来优化的算法。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。原文中提出该算法的复杂度为，是个比较小的系数，但该结论被证明不适于于所有情况。
Pascal语言示例
 1 Begin 2   initialize-single-source(G,s); 3   initialize-queue(Q); 4   enqueue(Q,s); 5   while not empty(Q) do 
 6     begin 7       u:=dequeue(Q); 8       for each v∈adj[u] do 
 9         begin10           tmp:=d[v];11           relax(u,v);12           if (tmp<>d[v]) and (not v in Q) then13             enqueue(Q,v);14         end;15     end;16 End;
C++语言示例
 1 int SPFA(int s) { 2 queue<int> q; 3 bool inq[maxn] = {false}; 4 for(int i = 1; i <= N; i++) dis[i] = 2147483647; 5 dis[s] = 0; 6 q.push(s); inq[s] = true; 7 while(!q.empty()) { 8 int x = q.front(); q.pop(); 9 inq[x] = false;10 for(int i = front[x]; i !=0 ; i = e[i].next) {11 int k = e[i].v;12 if(dis[k] > dis[x] + e[i].w) {13 dis[k] = dis[x] + e[i].w;14 if(!inq[k]) {15 inq[k] = true;16 q.push(k);17 }18 }19 }20 }21 for(int i =  1; i <= N; i++) cout << dis[i] << ' ';22 cout << endl;23 return 0;24 }