Bellman-Ford算法简介

Author: 2015-08-23

ACM

, ,

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