设计单源最短路径问题的算法[重复]

Question

这个问题在这里已有答案：

• Design an algorithm for the single source shortest path problem that runs in time O(k(|V|+|E|)) 1回答

假设有向图G =（V，E）具有潜在的正和负边长，但没有负循环。设s∈V是给定的源顶点。如何设计一个在时间O k（| V | + | E |）运行的单源最短路径问题的算法，如果从s到任何其他顶点的最短路径最多需要k个边缘，我们不知道什么是k。

Answer 1

这里是O（k（| V | + | E |））方法：

1. 我们可以使用Bellman-Ford算法进行一些修改
2. 创建数组D []以存储从节点s到某个节点u的最短路径
3. 最初D [s] = 0，所有其他D [i] = + oo（无穷大）
4. 现在我们遍历所有边缘k次并放松它们之后，D [u]在<= k边缘之后保持从节点s到u的最短路径值
5. 因此，如果在某些迭代中我们不能放松任何边缘，这意味着我们已经达到迭代k + 1并且我们可以终止算法，因为缩短路径将不会改善 伪代码：

      for each vertex v in vertices:  
          D[v] := +oo  
   
    D[s] = 0  
    lastRelaxation = 0  
       for i in [1,n]:  
       {  
        for each edge (u, v) with weight w in edges:  
              if D[u] + w < D[v]:  
                 {   
                 D[v] = D[u] + w  
                 lastRelaxation = i  
                 }  
        if lastRelaxation != i) break;
       }