Bellman-Ford算法简介

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

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

function BellmanFord(list vertices, list edges, vertex source)
   ::distance[],predecessor[]

   // This implementation takes in a graph, represented as
   // lists of vertices and edges, and fills two arrays
   // (distance and predecessor) with shortest-path
   // (less cost/distance/metric) information

   // Step 1: initialize graph
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := inf
       predecessor[v] := null

   // Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge (u, v) in Graph with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // Step 3: check for negative-weight cycles
   for each edge (u, v) in Graph with weight w in edges:
       if distance[u] + w < distance[v]:
           error "Graph contains a negative-weight cycle"
   return distance[], predecessor[]

  算法的输入为图中的顶点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步的操作,如果发现还有顶点的距离得到更新,则说明图中包含负权环。