设计求解单源最短路径问题的算法

Question

假设一个有向图G= (V，E)具有潜在的正负边长，但没有负圈。设s∈V是给定的源顶点。如果从s到任何其他顶点的最短路径至多需要k条边，并且我们不知道k是什么，那么如何设计一个算法来求解运行时间为O k(|V |+ |E|)的单源最短路径问题。

Answer 1

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

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

• Create数组来存储从节点s到某个节点u的最短路径

• 最初是Ds=0，以及所有其他的Di=+oo (无穷大)

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

• 之后保存从节点s到u的最短路径值因此，如果在某些迭代中我们不能松弛任何边，这意味着我们已经到达迭代k+1，我们可以终止算法，因为最短路径不会改善

伪码：

对于顶点中的每个顶点v: Dv := +oo Ds =0 lastRelaxation =0 for i in 1，n：{对于边中权重为w的每条边(u，v)：if Du +w< Dv：{ Dv = Du +w lastRelaxation =i} if lastRelaxation != i)断开；}