Bellman-Ford 算法

Bellman-Ford 算法¹ 同 Dijkstra 最短路径算法一样是求解带权有向无环图中从一个源节点到目标节点的最短路径问题。不同与 Dijkstra 每次取最近的点进入集合再更新距离，Bellman-Ford 算法每次都是循环所有的边，更新所有边的终点距离，有点类似与 BFS，Bellman-Ford 从源节点一圈一圈的向外更新。优点是算法可以处理负数权重的边，缺点是时间复杂度高于 Dijkstra 最短路径算法。

其大概过程用伪码表示：

procedure BellmanFord(list vertices, list edges, vertex source)
   // 讀入邊和節點的列表
   // 初始化圖distance為∞，predecessor為空
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null
   // 對所有節點
   for i from 1 to size(vertices)-1:
        //檢查每條邊
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // 檢查是否有負權重的迴路
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "圖包含負權重的迴路"

算法的复杂度为：

-	复杂度
最坏时间复杂度	$O(V\cdot E)$
最优时间复杂度	$O(E)$
空间复杂度	$O(V)$

Footnotes

1. Wikipedia ↩