BellmanFord算法在python中的实现

Question

我正在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

Answer 1

所以，我找到了这个练习的解决方案，很简单。问题是使用float（'inf'）初始化dist列表。如果我使用一个巨大的数字，比如10000000，它在我的初始代码中运行良好，而不需要扫描所有的顶点。它在一个非连通图的例子中起到了算法的作用。谢谢你的帮助，我学到了很多！在

Answer 2

此代码不适用于未连接的图形 例如，对于以下情况，它给出了1，这是正确的：

edges = []
edges.append([0, 1, 5])
edges.append([2, 3, -5])
edges.append([3, 4, -6])
edges.append([4, 2, -5])
edges.append([1, 2, 5])

print(bellmanFord(5, edges))

指向演示的链接：http://ideone.com/j8XAs3

当我们移除边1->；2时，它给出0，即使图有一个负循环（2->；3->；4->；2）：

^{pr2}$

指向演示的链接：http://ideone.com/N4Bljk

---

编辑：

正如您所说的测试用例12在您使用每个顶点作为源之后通过的，我确实认为该图是不连通的，问题是解决方案的时间复杂性增加了现在是O(n*n*m)，即大约10^11个操作肯定会超时。在

因此，您可以按以下方式修改算法：

1）找到所有连接的组件，分离出该组件的顶点和边，并用这些顶点和边创建一个新的图

2）假设你现在有k个新的图形，对每一个都运行Bellman Ford。在

另外，你用“强连通”这个词是错误的，有向图是强连通的，如果从每个顶点到每个其他可能的顶点都有一条路径。在

我看到了你所指的问题，我假设它是“问题：检测货币汇率的异常”，如果我对这个问题是正确的，那么问题中给出的例子与它是强连接的事实相矛盾的，因为没有办法到达顶点4，但是图是连接的。在

问题中的示例：

4 4
1 2 -5
4 1 2
2 3 2
3 1 1

如果这不是你所指的问题，或者你还有其他疑问，请告诉我。在