Bellman–Ford算法

与其他最短路方法一样，算法先把源点距离置零，把其他距离置为无穷大。每次松弛边u到v，都检查通过u形成的累计费用是否更小，必要时更新v的距离和前驱。

基础形式反复扫描全部边。一次扫描获得的改进继续参与后面的传播；经过足够轮次后，所有不需要负环绕行的最短路径都能得到相应更新。它不要求像标准Dijkstra那样每次永久确定一个当前最小的顶点。

参考：[1]

单条负边只是减少一段路径的累计费用，并不自动使最短路无法定义。没有相关负环时，最短路径可取不重复顶点的形式，边数至多为顶点数减一，这给重复松弛提供了轮次依据。

若足够轮次以后，从源点可达的部分仍可继续降低距离，就需要检查负环。负环若还能通向某个目标，反复绕行便可持续减少到达该目标的费用；这时应报告相应问题，而不是给出一个看似完成的有限距离。

参考：[1]

队列形式把距离刚发生变化的顶点加入待处理集合，只重新检查可能带来新改进的出边。记录一个顶点是否已在队列中，可以避免同一工作被重复排队；负环检测仍须按正确规则保留。

这种优化常减少实际工作，但一般最坏时间上界仍为O(VE)，不能把某个小样本跑得快当作普遍线性保证。源点不可达的负环也应与可达问题分开；最终的路径、错误状态和资源评估都要明确查询范围。

参考：[1]