赞
踩
与Dijkstra算法不同,Bellman-ford能对付有负权重的边,而且可以检测negative cycle.
假设V存的是所有的顶点(vertex),E存的是所有的边(edge),w(u, v)代表顶点u到顶点v的权重,PI[v]存的是从哪一个顶点到顶点v(PI[A]=s表示s->A)
以这幅图为例子。
伪代码
for v in V:
d[v]=INFINITY
PI[v]=''
d[s]=0
for i in range(1, len(V)): # 从i到len(V)-1
for w(u,v) in E:
# relax操作
if d[v] > d[u] + w(u,v):
d[v] = d[u] + w(u,v)
PI[v] = u
那种每次循环一遍d[v]都会减少的,循环无数次后,d[v]会趋近于负无穷。
for w(u,v) in E:
if d[v] > d[u] + w(u,v):
return negative_cycle_error
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。