algorithm - 设计用于单源最短路径问题的算法

This question already has an answer here:

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是什么。

最佳答案

这里是o（k（v+e）方法：
我们可以使用bellman-ford算法进行一些修改
创建数组D[]以存储从节点s到某个节点u的最短路径
最初d[s]=0，所有其他d[i]=+oo（无穷大）
现在，在我们遍历所有边k次并放松它们之后，d[u]在因此，如果在某些迭代中，我们不能放松任何边，这意味着我们已经达到了迭代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;
    }

关于algorithm - 设计用于单源最短路径问题的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55123504/