Bellman-Ford算法在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

此代码不适用于未连接的图形，例如，对于以下情况，它会给出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)：

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

print(bellmanFord(5, edges))

演示链接：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

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

Answer 2

所以，我找到了这个练习的解决方案，而且非常简单。问题是使用float('inf')初始化dist列表。如果我使用一个很大的数字，比如10000000，它在我的初始代码上工作得很好，而不需要扫描所有的顶点。在未连接图的示例中，它的工作方式也是如此。谢谢你的帮助，我学到了很多！