1

我有以下问题。我有循环、无向、加权图 G=(V,E)。我需要根据这些规则找到两个给定节点之间的简单路径（没有循环）：

  1. 在每个可能路径的边集中找到最小权重值
  2. 选择这条路径，它在从找到的路径中选择的最小值中具有最大最小值

例如，我们有如下图表：

示例图

我们可以尝试找到从节点 1 到节点 8 的简单路径。有两种可能的路径，如下所示：

  1. 1 -> 3 -> 5 -> 8，这条路径上的最小边权重是 2
  2. 1 -> 3 -> 5 -> 6 -> 7 -> 8，这条路径上的最小边权重是 283

根据提出的标准，想要的路径是路径号 2，因为它具有比路径号 1 更大的最小值。

一个重要的假设：图中的节点数量非常少：少于 15 个。

我考虑过 Dijkstra 或 Bellman-Ford 算法修改，但挑战是，我们没有局部标准（最小距离） - 我们无法找到最小的边权重，直到我们没有获得整个路径......

我的第二个想法是使用最近邻算法的修改，但它用于解决所谓的旅行商问题，与我的情况相比有点不同。

我的问题如下。解决这个问题是否比使用深度优先算法获得两个给定节点之间的所有直接非循环简单路径，然后选择每个找到的路径的最小权重值的最大值更好？

在这种情况下，我有点担心 DFS 算法的复杂性，尤其是由于图中的递归和可能连接（边）的数量。

谢谢你的任何想法。

4

2 回答 2

3

在最小边权重上使用二分搜索：

假设您的搜索间隔是[m, M]。对于一个设定值L = (m + M) / 2，使用BFS或DFS来找到一条从source到的路径，destination这样所有的边都有权重>= L。如果可以，请设置m = L + 1并重复搜索。如果您无法执行此操作，请设置M = L - 1并重复搜索。

这将是O((edges + nodes) log maxEdgeWeight)。对于您的少量节点应该非常快。

请注意，通过使用Dijkstra 算法和计数排序的思想，也有一种方法可以不使用对数因子。但是对于这么少的节点，你绝对不需要这个。

更新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（在您的情况下只有一个）。

于 2013-08-27T15:03:12.770 回答
2

找到一个最大生成树（通过优先级队列/排序顺序颠倒的常用算法）并在其中采用唯一路径。如果在它的端点之间有一条由更大的边组成的路径，那么这条路径上的最小边永远不会被添加到树中，如果有更好的整体路径就会有。

于 2013-08-27T15:36:42.963 回答