最短路径,一条边变为零

Question

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

什么是最有效的算法,从头到尾找到最短路径,能够将一个边的权重转为零？

编辑:我知道dijkstra算法,但正如我所说,这个问题的情况不同:我们被允许将一个边缘变为零,

我想知道如何有效地解决这个问题,实际上,一种方法是迭代地将边缘权重转为零!并且每一步都应用dijkstra算法,但是,我正在寻找更有效的方法

谢谢

Answer 1

你可以通过在两倍大小的增强图上使用Djikstra算法来解决这个问题.

假设你有顶点1 ... n.

定义一个新的图形,使得对于原始中具有权重w的每个边a-> b,定义具有权重w的a-> b的边,具有权重0的a-> b + n,以及具有权重0的a + n-> b + n.重量w.

想法是顶点n + 1..n + n是包含原始图的副本的重复.从原始移动到复制表示使用您将边缘转换为0的特殊能力.请注意,一旦复制,就无法返回到原始图形,因此这种特殊能力只能使用一次.

因此,您只需解决从开始到结束+ n的增强图上的问题,找到最短路径,包括将单个权重设置为0的能力.