算法札记 - 带负权边的最短路径 - Bellman-Ford算法

bellman-Ford算法

核心代码部分
栗子

一般来说，Bellman-Ford算法只需要$n?1(n为顶点数)$松弛就可以了。在每一个阶段，我们都会对每一套边进行松弛操作，而每实施一次松弛操作，就会有一些顶点已经求得其最短路径，此后这些顶点的最短路径值就会保持不变。经过$k$个阶段，就已经找出了从原点出发最多经过$k?1$条边到达其余顶点的最短路径。

Bellman-Ford算法的时间复杂度为$O(nm)$，包括n次对边集合的松弛操作，边集合的大小为m.

判断负权回路

如果进行$n?1$次松弛操作之后，任然存在：

换句话说就是在进行$n?1$次松弛操作之后任然可以再继续成功地进行松弛操作，那么此图必然存在负权回路。

优化

从Bellman-Ford的时间复杂度上来看，对于多顶点的稠密图来说其效率将大大下降，因此我们给出下面两种优化方式：

1. 在实际操作中，经常可能在为到达$n?1$轮时已经得出了需要的最短路径，因此，我们可以添加一个数组用来备份$dis[...]$数组，如果在新一轮的松弛中$dis[...]$数组的值没有发生变化，即可提前调出循环。

2. 由前文论述可知，在每一次松弛操作之后就会有一些顶点已经得到了最短路径，但是在往后每次松弛操作中还是要判断是否需要进行松弛。因此，每次仅对最短路径估计值发生了变化的顶点的所有出边进行松弛操作。

• 数据结构（十一）：最短路径(Bellman-Ford算法)
• 【啊哈！算法】最短路径之Bellman-ford算法
• Bellman-ford（解决负权边）
• 最短路径（三）—Bellman-Ford算法（解决负权边）