贝尔曼-福特算法
贝尔曼-福特算法
贝尔曼-福特算法（），求解单源最短路径问题的一种算法，由理查德·贝尔曼和小莱斯特·伦道夫·福特创立。有时候这种算法也被称为贝尔曼-福特-摩尔算法（Bellman–Ford–Moore algorithm），因为爱德华·F·摩尔也为这个算法的发展做出了贡献。它的原理是对图进行formula_1次松弛操作，得到所有可能的最短路径。其优于戴克斯特拉算法的方面是边的权值可以为负数、实现简单，缺点是时间复杂度过高，高达formula_2。但算法可以进行若干种优化，提高了效率。
算法.
贝尔曼-福特算法与戴克斯特拉演算法类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。
然而，戴克斯特拉演算法以贪心法选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作；而贝尔曼-福特算法简单地对所有边进行松弛操作，共formula_3次，其中formula_4是图的点的数量。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比戴克斯特拉演算法适用于更多种类的输入。
贝尔曼-福特算法的最多运行formula_5（大O符号）次，formula_6和formula_7分别是节点和边的数量）。
伪代码.
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 d[v]) and (not v in Q) then
enqueue(Q,v);
end;
end;
End;
C++语言示例
int SPFA(int s) {
std::queue q;
bool inq[maxn] = {false};
for(int i = 1; i dis[x] + e[i].w) {
dis[k] = dis[x] + e[i].w;
if(!inq[k]) {
inq[k] = true;
q.push(k);
for(int i = 1; i <= N; i++) std::cout « dis[i] « ' ';
std::cout « std::endl;
return 0;
样例.
例：
formula_15，formula_16。
运行如表： formula_17
本站由爱斯园团队开发维护，感谢那些提出宝贵意见和打赏的网友，没有你们的支持，网站不可能发展到今天，
继往开来，善终如始，我们将继续砥砺前行。
Copyright ©2014 iissy.com, All Rights Reserved.