Bellman-ford算法图解

介绍

与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]=INFINITYPI[v]='' d[s]=0

循环

for i in range(1, len(V)): # 从i到len(V)-1for w(u,v) in E:# relax操作if d[v] > d[u] + w(u,v):d[v] = d[u] + w(u,v)PI[v] = u

检查有没有negative-weight cycle

什么是negative-weight cycle？

那种每次循环一遍d[v]都会减少的，循环无数次后，d[v]会趋近于负无穷。

for w(u,v) in E:if d[v] > d[u] + w(u,v):return negative_cycle_error

总结

以上是生活随笔为你收集整理的Bellman-ford算法图解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。