设计了一个求解时间为O(k(|V|+|E|))的单源最短路径问题的算法

Question

假设我们有一个有向图G = (V, E)，它可能有正负的边长，但没有负圈。假设s ∈ V是给定的源顶点。如果从s到任何其他顶点的最短路径至多需要k edges，如何设计一个算法来求解在时间O(k(|V | + |E|))内运行的单源最短路径问题

Answer 1

这里是O(k(|V |+ |E|))方法：

我们可以使用贝尔曼-福特算法和一些modifications

• Create数组来存储从节点s到某个节点u的最短路径，最初是Ds=0，然后是所有其他的Di=+oo (无穷大)

• 现在在我们遍历所有边k次并松弛它们之后，Du在<=k

• 之后保存从节点s到u的最短路径值因为任何s-u最短路径至多是k条边，我们可以在k次迭代后结束算法

伪码：

对于顶点中的每个顶点v：

Dv := +ooDs =0重复k次：

对于边中具有权重w的每个边(u，v)：

如果Du +w< Dv：

Dv = Du + w