接上文
Bellman-Ford算法是一种通用最短路径算法, 其可处理权重为负值以及包括环的图类型.对于位于负权值环上的点, 其最短路径不存在.因此使用Bellman-Ford算法进行最短路径搜索时,需要判断是否存在负权重环.

Bellman-Ford算法如下:

在任意函数V个顶点的加权有向图中, 给定起点s, 从起点s无法到达图中的任一负权重环, 则使用以下方法能构找到起点s到所有可达顶点的最短路径.
将distTo[s]设为0, 数组中其余元素设为正无穷大. 以任意顺序松弛图中的所有边, 重复V轮.

证明:
Bellman-Ford算法核心思想为对于长度为k的最短路径,对所有边以任意顺序进行松弛k轮即可搜索得到该最短路径.
使用归纳法证明如上结论.

设从起点$s$到达顶点$t$的最短路径为$s=v_0->v_1->...->v_{k-1}->v_k=t$,
1.当k等于0时, 结论显然成立.
2. 设经过$k-1$轮松弛, 所有长度为$k-1$的最短路径已经被搜索得到.则此时$distTo[v_{k-1}]$值为从$s$到节点$v_{k-1}$的最短路径.在第$k$轮松弛中, $distTo[v_k]$的值肯定会被边$v_{k-1}->v_k$松弛, 因此$distTo[v_k]<=distTo[v_{k-1}]+W_{v_{k-1},v_k}$.又因为$distTo[v_k]$肯定不会小于最短路径长度, $distTo[v_k]>=distTo[v_{k-1}]+W_{v_{k-1},v_k}$, 因此$distTo[v_k]=distTo[v_{k-1}]+W_{v_{k-1},v_k}$, 因此$distTo[v_k]$即为起点$s$到节点t的最短路径. 则在经过$k$轮松弛后, 长度为$k$的最短路径被搜索得到.

由于起点$s$无法到达图中的任一负权重环, 因此起点$s$到其他所有顶点的最短路径不包括环,因此起点$s$到其他顶点的最短路径最多包括$V-1$条边.因此最多经过$V-1$轮松弛, 顶点$s$到其余顶点的最短路径便可搜索得到.

实际上, 在Bellman-Ford算法执行过程中, 每轮无需松弛所有边.只有当前节点的$distTo[]$值在上一轮发生变化(变得更小), 此轮对其邻边的松弛才有可能成功.如果$distTo[]$值未变化, 则对其邻边的松弛结果与前轮松弛结果一致, 无需重复进行.因此可以维护一个队列, 保存$distTo[]$值发生变化的顶点, 每轮迭代时只对这些顶点的邻边进行松弛.