给定一个无向加权图 G 和两个顶点:起始顶点和结束顶点
找到从开始到结束的最短路径并且能够将恰好一条边的权重变为零的最有效算法是什么？
编辑:
我知道 dijkstra 算法，但正如我所说，
这个问题的情况有所不同:我们可以将一条边变成零，
我想知道如何有效地解决这个问题，
实际上，一种方法是将边权重迭代为零!并在每一步中应用 dijkstra 算法，
但是，我正在寻找更有效的方法
谢谢
最佳答案
您可以通过在两倍大小的增强图上使用 Djikstra 算法来解决此问题。
假设您有顶点 1...n。
定义一个新图，使得对于原始中权重为 w 的每条边 a->b，定义边 a->b 的权重为 w，a->b+n 的权重为 0，a+n->b+n 定义为重量 w。
这个想法是顶点 n+1..n+n 是包含原始图副本的副本。从原图移动到副本表示使用您将边变为 0 的特殊能力。请注意，一旦进入副本，就无法返回原始图形，因此该特殊能力只能使用一次。
因此，您只需要解决从开始到结束 + n 的增强图上的问题即可找到最短路径，包括您将单个权重设置为 0 的能力。
关于algorithm - 一条边变为零的最短路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14104718/