基于队列的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

您的非循环代码似乎是正确的，但这取决于您所说的one iteration to calculate the shortest path是什么意思。如果图是非循环的(例如，一个DAG)，那么拓扑排序将允许我们访问每个顶点v一次(在检查了它的所有前身之后)，并将dist[v]更新到它的最小距离。这是在线性时间O(V+E)内完成的。因此，您的DAG算法看起来应该与以下内容类似

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

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

什么时候我必须检查有没有一个负循环？

源s上的BF算法返回从s到每个其他顶点的最短路径，或者返回指示存在负循环的失败。在执行之后，如果有一条边没有放松，那么就会有一个负循环。

Answer 2

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

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

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

关于When i must check that there is a negative cycle?，您将再做一次迭代，如果最后一个数组(n-1-th iteration之后的数组)中的任何值发生变化，您将说有负周期，如果没有任何变化，则表明没有负周期。

这个youtube link用一个例子很好地解释了贝尔曼-福特。