一条边转向为零的最短路径

Question

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

最有效的算法是什么，它可以找到从头到尾的最短路径，并且能够将一条边的权重变为零？

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

谢谢

Answer 1

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

假设你有1…n个顶点。

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

其思想是顶点n+1..n+n是包含原始图的副本的副本。从原始图像移动到复制图像表示使用将边转换为0的特殊能力。请注意，一旦你在副本中，就没有办法返回到原始图形，所以这个特殊的能力只能使用一次。

因此，您只需要解决从start到end+n的增广图上的问题，就可以找到最短路径，包括将单个权重设置为0的能力。

Answer 2

Dijkstra's algorithm通常用于解决这些类型的问题。而且，这听起来有点像TSP的问题，尽管在这一点上我可能是错的。