这个问题是要从一个起点到图中的所有其他顶点寻找最短路径。
但该图将具有m个正权边和k个负权边，并且保证负权边不在环中。换句话说，这个图中没有负权环。
我尝试直接使用 Bellman-Ford 和 SPFA 来解决这个问题，但是否存在更快的方法来解决呢？
1个回答
3
如果 k 很大，你可能希望直接运行贝尔曼-福德算法并结束。
如果 k 较小，则可以从约翰逊算法中借用重新加权技巧，但初始化比仅运行贝尔曼-福德算法更快。回想一下，约翰逊为每个顶点计算了一个潜力 π(v)，并将每个弧 vw 的成本从 c(vw) 调整为 c′(vw) = c(vw) - π(v) + π(w)，选择 π 使得 c′ 没有负值。在 c 和 c′ 方面，s 和 t 之间的最短路径是相同的，
假设输入图 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 堆。
如果 k 较小，则可以从约翰逊算法中借用重新加权技巧，但初始化比仅运行贝尔曼-福德算法更快。回想一下，约翰逊为每个顶点计算了一个潜力 π(v)，并将每个弧 vw 的成本从 c(vw) 调整为 c′(vw) = c(vw) - π(v) + π(w)，选择 π 使得 c′ 没有负值。在 c 和 c′ 方面，s 和 t 之间的最短路径是相同的，
假设输入图 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 堆。
- David Eisenstat
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接