贝尔曼-福特算法

贝尔曼-福特算法，是一种图论算法，用于计算从边加权图中的起始节点开始的最短路径。 偶尔会提到摩尔-贝尔曼-福特算法。

与 Dijkstra 算法（在图中寻找最短路径的最著名方法）不同，此处边的权重也可以为负。 但是，必须排除可以从起始节点到达的负权重循环，因为否则它们可以运行任意次数并且可以构建权重越来越低的路径，因此根本不存在权重最低的路径. 贝尔曼-福特算法可以检测负权重循环的存在。

G 表示具有节点集 V  和边集 E 的加权图。 权重指定两个节点之间的边的权重。 s 是计算到所有其他节点的最短路径的起始节点，而 n 是 V 中的节点数。

当算法执行结束时，输出显示 G是否有负长度循环。 如果不是这种情况，则每个节点的距离包含它到 s的距离，即从 s 开始的最短路径的权重。 生成树也是前人定义的，它以树内的形式存储从 s 开始的最短路径。 从一个节点开始，通过递归访问前人给出的节点，直到到达 s  ，可以向后确定相应的最短路径。

一条没有循环的路径最多包含 n 个节点，即 n − 1 条边。 因此，如果在第 10 行中确定路径不是最优路径，则它必须包含负权重的循环。

算法的正确性可以通过归纳来证明。

如果没有权重为负的环，则每条最短路径最多包含每个节点一次，因此第 09 行到第 11 行无法进一步改进。 相反，假设无法进行任何改进。 然后对于节点 v 0 , … , v k − 1 {\displaystyle v_{0},\ldots ,v_{k-1}} 的每个循环：

D i s t a n c e ( v i ) ≤ D i s t a nc e ( v ( i − 1 mod k ) ) + w e h t ( v ( i − 1 mod k ) , vi i )

在循环中求和，然后是项 D i s t a n c e ( v i )

也就是说，每个循环都有一个非负权重。

贝尔曼-福特算法的运行时间为 O ，其中 n 是节点数，m 是图中的边数。

如果你想找到从每个节点到每个其他节点的最短路径，你必须为每个起始节点应用一次算法，即总共 n 次。 因此，运行时复杂度为 O。

比贝尔曼-福特算法更快的是 Dijkstra 算法，这是一种寻找最短路径的贪婪算法，它连续地将优先级队列中的下一个最佳节点包含在结果集 S 中。 它的运行时间为 O 。 然而，它的缺点是它只接受具有非负权重的图作为输入。

A* 算法通过估计函数扩展了 Dijkstra 算法，并具有运行时间 O ( n 2 )。

另一种寻找最短路径的方法是 Floyd-Warshall 算法，它基于像贝尔曼-福特算法这样的动态规划。 两者的正确性都基于贝尔曼的最优性原则。

贝尔曼-福特算法用于距离矢量算法，一种动态路由算法等。 这将 z。 例如，路由信息协议使用它，该协议在管理网络域（内部网关协议）内动态创建路由表。

贝尔曼-福特算法的分布式变体用于距离矢量路由协议，例如路由信息协议。 该算法是分布式的，因为它涉及自治系统内的许多节点（路由器），自治系统是通常由 Internet 服务提供商拥有的 IP 网络的集合。