两节点间最小化最大权重路径的算法

Question

两节点间最小化最大权重路径的算法

algorithmgraphgraph-algorithmshortest-path

9

我希望能开车从城市X到城市Y。我的车油箱很小，加油站只存在于道路交叉口（交叉口是节点，道路是边缘）。因此，我想走一条路径，使我在两个加油站之间行驶的最大距离最小化。有没有更有效的算法可以用来找到这条路径？暴力搜索是一个不好的解决方案。我想知道是否存在更有效的算法。

- Traveling Salesman

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- kraskevich · Accepted Answer

这里有一个简单的解决方案：

按照它们的权重对边进行排序。
从最轻的边开始逐个添加，直到 X 和 Y 连接为止。
要检查它们是否连接，可以使用并查集数据结构。

时间复杂度为 O(E log E)。

正确性证明：

正确答案不会比此解决方案返回的答案更大。这是因为该解决方案是构造性的：一旦X和Y在同一组件中，我们可以明确地写出它们之间的路径。它不能包含更重的边，因为它们还没有被添加。
正确答案不会比此解决方案返回的答案更小。假设X和Y之间存在一条路径，其由权重严格小于返回的答案的边组成。但是这是不可能的，因为所有更轻的边都已经被处理过了（我们按照排序顺序进行迭代），而且X和Y在不同的组件中。因此，它们之间没有路径。

1）和2）说明了此算法的正确性。

此解决方案适用于无向图。

以下是解决有向情况问题的算法（它也适用于无向图）：

让我们按照它们的权重对边进行排序。
让我们在路径中二分查找最重边的权重(由所有边的排序列表中的边的索引确定)。
对于固定的答案候选i，我们可以执行以下操作:
1. 将所有索引小于i的边添加到已排序列表中(即所有不比当前边更重的边)。
2. 运行DFS或BFS以检查是否存在从X到Y的路径。
3. 根据这样的路径的存在与否调整二进制搜索中的左右边界。

时间复杂度为O((E + V) * log E)(我们运行DFS/BFS log E次，每次都需要O(E + V)的时间)。

这是一个伪代码:

if (X == Y)
    return 0 // We don't need any edges.
if (Y is not reachable from X using all edges)
    return -1 // No solution.
edges = a list of edges sorted by their weight in increasing order 
low = -1 // definitely to small(no edges)
high = edges.length - 1 // definitely big enough(all edges)
while (high - low > 1) 
    mid = low + (high - low) / 2
    g = empty graph
    for i = 0...mid
        g.add(edges[i])
    if (g.hasPath(X, Y)) // Checks that there is a path using DFS or BFS
         high = mid
    else
         low = mid
return edges[high]