Bellman-Ford算法在python中的实现
Bellman-Ford算法在python中的实现
提问于 2017-01-07 11:12:08
我正在Coursera上做“图上的算法”课程的练习，我必须实现Bellman-Ford算法来检测图是否有负圈，分别输出1和0。我做了很多压力测试，我的实现运行良好，但在课程中的一个测试用例上失败了(但他们没有给出任何关于它的信息，除了“错误的答案”)。我的实现和你在网上看到的一样，因此我看不出我的代码有什么问题。有什么想法吗？
def relax(u,v,w,dist,prev):
if dist[u]+w < dist[v]:
dist[v] = dist[u]+w
prev[v] = u
def bellmanFord(V,E):
dist = [float('inf')] * V
prev = [None] * V
dist[0] = 0
for i in range(V-1):
for edge in E:
relax(edge[0],edge[1],edge[2],dist,prev)
#checks for negative cycles
for e in E:
u = e[0]
v = e[1]
w = e[2]
if dist[u]+w < dist[v]:
return 1
return 0回答 1
Stack Overflow用户
发布于 2017-01-09 00:32:39
所以，我找到了这个练习的解决方案，而且非常简单。问题是使用float('inf')初始化dist列表。如果我使用一个很大的数字，比如10000000，它在我的初始代码上工作得很好，而不需要扫描所有的顶点。在未连接图的示例中，它的工作方式也是如此。谢谢你的帮助，我学到了很多！
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/41517416
复制相关文章
相似问题