1

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

给定一个问题来搜索从源 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

我的问题是：

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

我什么时候必须检查是否存在负循环？谢谢

4

2 回答 2

2

您的非循环代码似乎是正确的，但取决于您所说的 .. 是什么意思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 算法的排队版本。v我只能说，只要您意识到一个顶点（即u）尚未完成，您就需要确保该顶点在队列中。所以你的代码应该enqueue和dequeue某些条件下的一些顶点（同时放松边缘）。我想你已经知道算法的非排队版本，这是显而易见的。

我什么时候必须检查是否存在负循环？

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

于 2014-11-17T09:21:40.293 回答
1

I don't remember details of Bellman-Ford, but basically, assume you have n edges and m vertex,

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

This part can be found on the internet easily.

Related to When i must check that there is a negative cycle?, you will do one more iteration and if any value in the last array(the array after n-1-th iteration) changes, you will say there is negative cycle, if nothing changes, it indicates there is no negative cycle.

This youtube link explains Bellman-Ford well with an example.

于 2014-11-17T10:14:39.803 回答