Bellman-Ford算法简介

  Bellman-Ford算法用于计算有向图中的单源最短路径。对于有V个顶点和E条边的图,Bellman-Ford的时间复杂度为O(V·E),效率低于Dijkstra算法。Bellman-Ford可以用于有负权边的情况,且能判断负权环,十分灵活。

  Wiki上给出的Bellman-Ford算法的伪代码如下所示:

  算法的输入为图中的顶点 list vertices 和边 list edges ,以及起点 vertex source ,输出为起点到所有其他点的最短距离 distance[] 和用于回溯路径的前驱 predecessor[] 。算法流程如下:

  1. 初始化到起点的距离 distance[source] 为0,到其他点的距离 distance[v], v != source 为无穷,所有前驱为空。
  2. 遍历所有的边,对于权值为w的边(u, v),如果该边能够使起点到v的距离缩短,即从起点先到u再由边(u, v)到v的距离,短于起点直接到v的距离( distance[u] + w < distance[v] ),则发现了一条更短的从起点到达v的路径,更新起点到v的距离 distance[v] 为 distance[u] + w ,并记录前驱( predecessor[v] := u )。
  3. 循环执行第2步的操作,对于第i次循环,算法可以成功找到最多包含i条边的最短路径,由于最长的路径可以包含V-1条边(V为顶点总数),则需要循环V-1次,才能确保起点到所有点的最短路径都被找到。
  4. 最后,再额外进行一遍第2步的操作,如果发现还有顶点的距离得到更新,则说明图中包含负权环。