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

Question

我想乘车从X市到Y市.我的车有一个小水箱,加油站只存在于道路交叉口(交叉口是节点,道路是边缘).因此,我想采取一条路径,使我在两个加油站之间行驶的最大距离最小化.我可以使用什么有效的算法来找到该路径？蛮力是一个坏的解决方案.我想知道是否存在更有效的算法.

Answer 1

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

1. 按重量对边缘进行排序.

2. 开始添加逐一(从最轻到最重的),直到X和Y成为连接.

3. 要检查它们是否已连接,可以使用union-find数据结构.

时间的复杂性是O(E log E).

证明正确性:

1. 正确答案不大于此解决方案返回的答案.这是这种情况,因为该解决方案是建设性的:一次X,并Y在相同的组件,我们可以明确地记下它们之间的路径.它不能包含较重的边缘,因为它们尚未添加.

2. 正确答案不小于此解决方案返回的答案.让我们假设在X和之间存在一条路径,Y该路径的权重严格小于返回的答案.但是不可能,因为之前处理了所有较轻的边缘(我们按照排序顺序迭代它们)X并且Y它们处于不同的组件中.因此,它们之间没有路径.

1)和2)暗示该算法的正确性.

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

这是一个解决定向案例问题的算法(它也适用于无向图):

1. 让我们按重量对边缘进行排序.

2. 让二进制搜索路径中最重边的权重(由所有边的排序列表中的边的索引确定).

3. 对于固定答案候选人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]