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