Bellman-Ford算法

Bellman-Ford 算法

Bellman-Ford算法是计算单源(single source vertex)最短路径的算法。相比较于 Dijkstra's algorithm 算法,BellmanFord算法较慢,但是却能适合有负权值的边,对于负环图(negative cycle)也能检测到其存在,这对于图计算/计算机网络路由算法都有重要的意义。

Bellman-Ford算法是基于松弛计算的(relaxation operation)

松弛计算 对于两点(A和B)以及连接他们的边,如果源节点S(source node)到第一个节点A的距离加上AB间的边的距离小于源节点S到第二个节点B的距离,那么A将作为B的先驱节点,源节点到B的距离也更新到(distance(A)+ edge.length(A,B)),否则不进行任何更新。

Bellman-Ford算法可以大致分为三个部分 1. 初始化所有点。每一个点保存一个值,表示从原点到达这个点的距离,将原点的值设为0,其它的点的值设为无穷大(表示不可达)。 2. 进行循环,循环下标为从1到n-1(n等于图中点的个数)。在循环内部,遍历所有的边,进行松弛计算。 3. 遍历途中所有的边(edge(u,v)),判断是否存在这样情况: d(v) > d (u) + w(u,v),则返回false,表示途中存在从源点可达的权为负的回路

function <predecessors> Bellman-Ford(G, source)
for i in 1 to |U| do
distance[i] = +inf
predecessors[i] = null

distance[source] = 0

for i in 1 to (|U| - 1) do
for each Edge e in Edges(G) do
if distance[e.from] + length(e) < distance[e.to] do
distance[e.to] = distance[e.from] + length(e)
predecessors[e.to] = e.from

for each Edge e in Edges(G) do
if distance[e.from] + length(e) < distance[e.to] do
error("Graph contains cycles of negative length")

return predecessors

这里的第三步是为了检测是否存在negative cycle,假设存在以下图并进行relaxation operation:

由于存在negative edge 导致每进行一次松弛计算,节点的权值都会减小,这样在环图中就没有收敛,此时根据算法第三条进行判断,若满足条件则说明存在negative edge

example