Bellman-Ford算法在python中的实现

我正在为Coursera上的“Graphs算法”课程做练习，我必须实现Bellman-Ford算法来检测图形是否有负循环，输出1和0。我做了很多压力测试，并且我的实现工作正常，但它在课程的一个测试用例中失败（但除了“错误答案”，他们没有提供任何有关它的信息）。我的实现与您在网上找到的完全一样，因此我看不出我的代码出了什么问题。有任何想法吗？Bellman-Ford算法在python中的实现

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

来源

2017-01-07 tortov

他们不测试空图，是吗？ –

或者一个没有强连接的图？ –

输入浮点或整数中的权重是多少？它保证图形连接？ – kraskevich

此代码不会为没有连接图形工作例如，它提供了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，但是图形连接。

例中的问题：

不要让我知道，如果不是你指的是这个问题，或者如果你有一些其他的疑惑。

来源

2017-01-07 15:35:18 uSeemSurprised

感谢您的回答uSeemSurprised。其实我错了，所有的图表都必须紧密联系。如果我理解的很好，Bellman-Ford算法是一种单源最短路径算法，所以这意味着它只能找到连接到源的负循环。但是你的文章帮助我了解了这个问题。将BellmanFord函数应用于每个顶点作为源，我能够通过练习（＃12），上升到＃18，但失败了，因为它花费了太多时间。可能我的代码没有检测到正确的距离，并在强连通的图中留下了一些顶点。 – tortov

再次感谢您的回答。这是有问题的问题。我做了一个可达性函数，用组号来标记每个节点。所以在这个例子中，如果我从1开始，顶点1,2,3将被标记为“0”，并且4将被标记为“1”。如果开始是4，那么每个人都将在组“0”上。在这两种情况下，它的作品然后，我在ech组的第一个成员中运行bellmanFord。有了这个，我能够通过案例＃12，但再次陷入案件＃18。这一次只花了0.13秒，得到了“错误的答案”。由于我花费的时间，我认为它正在检测一个假阴性周期。 – tortov

如果我按照相反的顺序运行bellmanFord，从最后一组开始，程序再次在代码＃12处失败，但现在由于超时而失败。如果它发现一个负循环，它立即返回，这就是情况＃18必须发生的事情。＃12和＃18都必须有大量的顶点和边。无论如何，现在我必须找到一个使其失败的测试用例。这里是更新的代码：[http://ideone.com/cczJjq]（http://ideone.com/cczJjq） – tortov

所以，我找到了锻炼的解决方案，它非常简单。问题是使用float（'inf'）来初始化dist列表。相反，如果我使用一个庞大的数字，比如10000000，它可以在我的初始代码上正常工作，而不需要扫描所有的顶点。它在一个没有连接的图的例子中起作用。感谢帮助，我学到了很多！

来源

2017-01-08 16:32:39 tortov

使用无穷始终是一个好主意，因为您可能不知道值有多大，请尝试在我提供的链接中给出的python代码，它是一个非常干净的方式，链接：http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/ – uSeemSurprised

Bellman-Ford算法在python中的实现

回答

相关问题