基于队列的Bellman-Ford算法

Question

我在试图理解这个算法是如何工作的。

给定一个问题，搜索从源s到图中所有顶点的路径，

我想我必须这样做：

if no cycle in the graph: 
     topological sort of the graph 
     one iteration to calculate the shortest path

else if there is a cycle in the graph:
     put s in the queue 
     v=q.deque
     while q is not empty
        relax v

我的问题是:

我的程序是好的还是我必须改变它。

当我必须检查是否存在负循环时？非常感谢。

Answer 1

我不记得贝尔曼福特的细节，但基本上，假设你有n边和m顶点，

for e = 1 to n-1
     iterate tru each vertex and apply the formula

这一部分可以很容易地在互联网上找到。

当我必须检查是否存在负循环时，与相关 ，您将再进行一次迭代，如果最后一个数组（第n-1次迭代后的数组）中的任何值发生变化，您将说存在负循环，如果没有变化，则表示没有负循环。

这个youtube链接用一个例子很好地解释了贝尔曼·福特。

Answer 2

非循环路径的代码似乎是正确的，但这取决于您所说的计算最短路径的一次迭代是什么意思。。如果图是非循环的（即DAG），那么拓扑排序将允许我们访问每个顶点v一次（在检查其所有前辈之后），并将dist[v]更新到其最小距离。这是在线性时间O（ve）内完成的。因此，您的DAG算法应该与此类似

  DAG_CASE:   
  topological sort of V
  for each u\in V following the topological sorting
    for each edge (u,v)
      relax(u,v) 

对于有向循环图的代码（没有负循环），您没有放松边，也没有更新/检查其endpoint。。我不熟悉BF算法的排队版本。我所能说的就是，当您意识到它的一个前辈（即u）尚未完成时，您需要确保顶点v在队列中。因此，在某些条件下（在放松边的同时），代码应该排队和出列一些顶点。我想你已经知道了算法的非排队版本，这是显而易见的。

当我必须检查是否存在负循环时？

通过一个源代码的BF算法返回从代码到其他顶点的最短路径，或者返回一个失败，表明有一个负循环。执行后，如果有一个边缘没有放松，那么就有一个负循环。