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