algorithm - 如何找到具有 k 个负加权边的最短路径？

Question

问题是到寻找最短路径 从开始顶点到 directed graph 中的所有其他顶点.
但图中会有m positive加权边和 k negative加权边，并且保证负加权边不会在一个循环中。换句话说，该图中没有负加权循环。
我试过直接用Bellman-Ford和 SPFA来解决这个问题，但有没有更快的方法来做到这一点？

Answer 1

如果 k 足够大，您可能应该运行 Bellman-Ford 并收工。
如果 k 很小，您可以借用 Johnson 算法中的重新加权技巧，但其初始化速度比仅运行 Bellman-Ford 更快。回想一下，Johnson 计算每个顶点的潜在 π(v) 并将每个弧 vw 的成本从 c(vw) 调整为 c′(vw) = c(vw) − π(v) + π(w)，选择 π所以 c' 绝非负数。 s 和 t 之间的最短路径对于 c 和对于 c' 相同，
假设输入图 G 恰好有一个负弧，假设 c(xy) < 0。使用 Dijkstra 算法计算 G − xy 中从 y 到所有其他顶点的距离。然后定义 π(v) = distance(y, v)。正确性证明遵循约翰逊算法的证明；弧 xy 不能是从 y 开始的最短路径的一部分，因为没有负循环，所以 G - xy 上的 Dijkstra 实际上计算了 G 的最短路径树。
对于一般 k，我们可以递归地执行此操作。如果 k = 0，则运行 Dijkstra。否则，删除负弧并递归计算最短路径，而不是使用 Dijkstra。一旦我们有好的 π 值，从给定的起始顶点再运行一次 Dijkstra。
总运行时间是 O((k + 1) (m + n log n)) 与 Fibonacci 堆。