<p>我正在Coursera上的“图上算法”课程做练习,我必须实现Bellman-Ford算法来检测一个图是否有负循环,分别输出1和0。我做了很多压力测试,我的实现工作得很好,但是在课程中的一个测试用例中却失败了(但是除了“错误答案”,他们没有给出任何关于它的信息)。我的实现和你在网上找到的一样,因此我看不出我的代码有什么问题。有什么想法吗?在</p>
<pre><code>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
</code></pre>