我有以下问题。我有循环的,无向的,加权图g=(v,e)。我需要根据以下规则找到两个给定节点之间的简单路径(无循环):
在每条可能路径的边集中求最小权值
选择此路径,在所选路径的最小值之间具有最大最小值
如下图所示:
我们可以尝试找到从节点1到节点8的简单路径有两种可能的路径,如下所示:
1->3->5->8,此路径上的最小边权重为2
1->3->5->6->7->8,此路径上的最小边权重为283
根据所提出的准则,所需路径是路径2,因为它比路径1具有更大的最小值。
一个重要的假设是:图中的节点数非常小:小于15。
我考虑过dijkstra或bellman-ford算法的修改,但挑战是,我们没有局部准则(最小距离)-我们无法找到边缘的最小权重,除非我们不能得到整个路径…
我的第二个想法是使用最近邻算法的修正,但它用于解决所谓的旅行商问题,这与我的情况有点不同。
我的问题如下。解决这一问题的方法是否比使用深度优先算法获得两个给定节点之间的所有直接非循环简单路径,然后选择每个找到的路径的最小权值的最大值更好?
在这种情况下,我有点担心DFS算法的复杂性,特别是由于递归和图中可能的连接(边)的数量。
谢谢你的意见。

最佳答案

在最小边缘重量上使用binary search
假设您的搜索间隔是[m, M]。对于设定值L = (m + M) / 2,使用BFSDFS查找从sourcedestination的路径,以便所有边都具有权重>= L如果可以,请设置m = L + 1并重复搜索。如果无法执行此操作,请设置M = L - 1并重复搜索。
这将是O((edges + nodes) log maxEdgeWeight)对于少量的节点应该非常快。
注意,也有一种方法可以在不使用对数因子的情况下,通过使用Dijkstra's algorithmcounting sort的思想来实现。但对于这么少的节点,您绝对不需要这个。
更新1:
下面是这对你的例子的作用首先,您的搜索间隔将是[2, 9000],因为它们分别是您的最小和最大边权重。

L = (2 + 9000) / 2 = 4501
=> Find a path from 1 to 8 such that all of its edges have weight >= 4501.
   This is not possible, so reduce the search interval to [2, 4500].

L = (2 + 4501) / 2 = 2251
=> Find a path from 1 to 8 such that all of its edges have weight >= 2251.
   This is not possible, reduce the search interval to [2, 2250]

L = (2 + 2250) / 2 = 1126
=> Not possible to find a path, reduce to [2, 1125]

L = (2 + 1125) / 2 = 563
=> Not possible, reduce to [2, 562]

L = (2 + 562) / 2 = 282
=> Success! We can find 1 -> 3 -> 5 -> 6 -> 7 -> 8
Mark 282 as the current best answer, and keep searching in [283, 562].

最终,你将得到283作为答案,这就是你想要的然后打印所有边权重>= 283的任何路径(在您的情况下只有一个)。

关于algorithm - 根据给定条件在图中找到两个节点之间的路径-优化任务,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/18468973/

10-12 02:40
查看更多