寻找最小化两个节点之间最大权重的路径的算法

Question

我想自驾从X市到Y市。我的车是小油箱，加油站只存在于路口（路口是节点，路是边）。因此，我想走一条路径，使我在两个加油站之间行驶的最大距离最小化。我可以使用什么有效的算法来找到该路径？蛮力是一种糟糕的解决方案。请问有没有更高效的算法

Answer 1

这是一个简单的解决方案：

按权重对边进行排序。
开始一个一个地添加它们（从最轻到最重）直到X和Y连接起来。
要检查它们是否连接，您可以使用 union-find 数据结构。

时间复杂度为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/BFSlog 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]

寻找最小化两个节点之间最大权重的路径的算法

Algorithm for finding the path that minimizes the maximum weight between two nodes

algorithm

graph

shortest-path

graph-algorithm