algorithm - 一条边变为零的最短路径

Question

给定一个无向加权图 G 和两个顶点:起始顶点和结束顶点

找到从开始到结束的最短路径并且能够将恰好一条边的权重变为零的最有效算法是什么？

编辑: 我知道dijkstra算法，但正如我所说， 这个问题的情况有所不同:我们可以将一条边变为零，

我想知道如何有效地解决这个问题， 实际上，一种方法是迭代地将边缘权重变为零!并在每一步应用迪杰斯特拉算法， 但是，我正在寻找更有效的方法

谢谢

Answer 1

您可以通过在两倍大小的扩充图上使用 Djikstra 算法来解决此问题。

假设您有顶点 1...n。

定义一个新图，使得对于原始中权重为 w 的每条边 a->b，定义权重为 w 的边 a->b，权重为 0 的 a->b+n 和 a+n->b +n 权重为 w。

想法是顶点 n+1..n+n 是包含原始图副本的副本。从原始图移动到副本表示使用将边变为 0 的特殊能力。请注意，一旦进入副本，就无法返回到原始图，因此此特殊能力只能使用一次。

因此你只需要解决从开始到结束+n 的增广图上的问题，以找到最短路径，包括你将单个权重设置为 0 的能力。