贝尔曼-福特算法（英语：Bellman–Ford algorithm），求解单源最短路径问题的一种算法，由理查德·贝尔曼和小莱斯特·伦道夫·福特创立。有时候这种算法也被称为 Moore-Bellman-Ford 算法，因为爱德华·F·摩尔也为这个算法的发展做出了贡献。它的原理是对图进行 | � | − 1 {\displaystyle |V|-1}次松弛操作，得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达 � ( | � | | � | ) O(|V||E|)。但算法可以进行若干种优化，提高了效率。
目录 1 算法 1.1 伪代码 2 原理 2.1 循环 2.2 负边权操作 2.3 负权环判定 3 查找负回路 4 优化 4.1 循环的提前跳出 4.2 队列优化 5 样例 6 参考文献 算法
在这个图中，假设A是起点，并且边以最坏的顺序处理，从右到左，需要 | � | − 1 {\displaystyle |V|-1}步或 4 4次计算路径长度。相反地，若边以最优顺序处理，从左到右，算法只需要在一次遍历内完成。 贝尔曼-福特算法与迪科斯彻算法类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。 然而，迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作；而贝尔曼-福特算法简单地对所有边进行松弛操作，共 | � | − 1 {\displaystyle |V|-1}次，其中 | � | {\displaystyle |V|}是图的点的数量。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。
贝尔曼-福特算法的最多运行 � ( | � | ⋅ | � | ) {\displaystyle O(|V|\cdot |E|)}（大O符号）次， | � | |V|和 | � | |E|分别是节点和边的数量）。
伪代码 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次循环操作保证了所有深度为n的路径最短。由于图的最短路径最长不会经过超过 | � | − 1 {\displaystyle |V|-1}条边，所以可知贝尔曼-福特算法所得为最短路径。
负边权操作 与迪科斯彻算法不同的是，迪科斯彻算法的基本操作“拓展”是在深度上寻路，而“松弛”操作则是在广度上寻路，这就确定了贝尔曼-福特算法可以对负边进行操作而不会影响结果。
负权环判定 因为负权环可以无限制的降低总花费，所以如果发现第 � n次操作仍可降低花销，就一定存在负权环。
查找负回路 当使用这个算法查找最短路径时，有负回路会使算法找不到正确的答案。但是，由于在找到负回路后会中止算法，所以可以被用来查找目标，例如在网络流分析中的消圈算法(Cycle Cancellation Algorithms)
优化 循环的提前跳出 在实际操作中，贝尔曼-福特算法经常会在未达到 | � | − 1 {\displaystyle |V|-1}次前就出解， | � | − 1 {\displaystyle |V|-1}其实是最大值。于是可以在循环中设置判定，在某次循环不再进行松弛时，直接退出循环，进行负权环判定。
队列优化 主条目：最短路径快速算法 西南交通大学的段凡丁于1994年提出了用队列来优化的算法。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，用一个队列记录松弛过的节点，可以避免了冗余计算。原文中提出该算法的复杂度为 � ( � | � | ) {\displaystyle O(k|E|)}， � k是个比较小的系数，[1]但该结论被证明不适于于所有情况。[来源请求]
Pascal语言示例
Begin initialize-single-source(G,s); initialize-queue(Q); enqueue(Q,s); while not empty(Q) do begin u:=dequeue(Q); for each v∈adj[u] do begin tmp:=d[v]; relax(u,v); if (tmp<>d[v]) and (not v in Q) then enqueue(Q,v); end; end; End; C++语言示例
int SPFA(int s) {
std::queue
�
{ � 1 , � 2 , � 3 , � 4 } , �
{ ( � 1 , � 2 ) , ( � 1 , � 3 ) , ( � 2 , � 4 ) , ( � 4 , � 3 ) } {\displaystyle V={v_{1},v_{2},v_{3},v_{4}},E={(v_{1},v_{2}),(v_{1},v_{3}),(v_{2},v_{4}),(v_{4},v_{3})}}， � � � � ℎ � ( � 1 , � 2 )
− 1 , � � � � ℎ � ( � 1 , � 3 )
3 , � � � � ℎ � ( � 2 , � 4 )
3 , � � � � ℎ � ( � 4 , � 3 )
− 1 {\displaystyle weight(v_{1},v_{2})=-1,weight(v_{1},v_{3})=3,weight(v_{2},v_{4})=3,weight(v_{4},v_{3})=-1}。 运行如表： � : Dist [ � ] , � : Pred [ � ] {\displaystyle D:{\texttt {Dist}}[v],P:{\texttt {Pred}}[v]}
点 � 1 v_1 � 2 v_2 � 3 v_3 � 4 {\displaystyle v_{4}} � / � {\displaystyle D/P} � / � {\displaystyle D/P} � / � {\displaystyle D/P} � / � {\displaystyle D/P} 初始化 0 / null {\displaystyle 0/{\texttt {null}}} ∞ / null {\displaystyle \infty /{\texttt {null}}} ∞ / null {\displaystyle \infty /{\texttt {null}}} ∞ / null {\displaystyle \infty /{\texttt {null}}} 循环第一次 0 / null {\displaystyle 0/{\texttt {null}}} − 1 / � 1 {\displaystyle -1/v_{1}} 3 / � 1 {\displaystyle 3/v_{1}} ∞ / null {\displaystyle \infty /{\texttt {null}}} 循环第二次 0 / null {\displaystyle 0/{\texttt {null}}} − 1 / � 1 {\displaystyle -1/v_{1}} 3 / � 1 {\displaystyle 3/v_{1}} 2 / � 2 {\displaystyle 2/v_{2}} 循环第三次 0 / null {\displaystyle 0/{\texttt {null}}} − 1 / � 1 {\displaystyle -1/v_{1}} 1 / � 4 {\displaystyle 1/v_{4}} 2 / � 2 {\displaystyle 2/v_{2}} 参考文献
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: