Bellman-Ford 算法

定义

Bellman-Ford 算法是一种单源最短路径算法,以 Richard Bellman 与 Lester Ford 的名字命名。与 Dijkstra 不同,它允许图中存在负权边。

原理

算法对图中所有边进行至多 V-1 轮松弛操作:若经过某条边能使终点的距离变小,就更新该距离。V-1 轮后若仍能松弛,说明图中存在从源点可达的负权环,此时最短路径无定义。时间复杂度为 O(VE)。

应用

用于含负权的最短路径问题、汇率套利检测(将汇率取对数转为负权环检测)、距离向量路由协议(如 RIP)的理论基础。

优缺点

优点是适用范围广、实现简单、可检测负环;缺点是复杂度高于 Dijkstra,在稠密大图上性能较差。队列优化的变体 SPFA 在稀疏图上通常更快,但最坏复杂度不变。