恢复时间最短的路径

Question

问题可以通过以下方式描述：

节点网络已崩溃，每个连接（边缘）都有一定的恢复时间，直到它重新联机并再次连接两个节点。我们的目标是找到最早运行的节点1到n之间的路径，并在该路径上返回最长的恢复时间。

网络可以表示为具有无向边的图。

我们有三个数组：

1. 第一个包含原点顶点
2. 第二个包含目标顶点
3. 第三个包含每个连接的恢复时间（边缘）

例：

{1,2,2,3}, {2,3,4,4}, {1,5,10,2}

其中节点1和2之间的连接恢复时间为1，等等。

从1到n = 4的最佳路径是1-2-3-4，因为与路径1-2-4相比，该路径上的最长恢复时间是5，其中最长恢复时间是10。

这里重要的是要注意，每条路径上最长的恢复时间才是最重要的，即路径的“长度”不是等待时间的总和，而是需要等待的最长时间的长度。两个节点之间的连接要恢复。每个恢复时间从t = 0计算，因此恢复时间是独立的，顺序无关紧要。

所以我们要做的就是找到每个路径上恢复时间最短的路径，并返回该时间。

我已经使用Dijkstra和Bellman-Ford算法解决了这个问题，但是无法真正解决如何修改算法以获得理想结果的问题。最多可以有10 ^ 5个连接。

Answer 1

这很容易使用DSU（https://en.wikipedia.org/wiki/Disjoint-set_data_structure）：

1. 按重量对所有边缘进行排序，增加
2. 循环通过边缘，节点u和v在不同的不相交集中，将它们合并成一个不相交的集合
3. 如果合并后节点1和N在同一集合中，则answer是当前边缘的权重，我们可以突破循环。

复杂性：O（E log E + V log V）

Answer 2

如Photon所述，DSU是最美丽的解决方案。

另一种可能的解决方案是使用二进制搜索+ dfs / bfs / Dijkstra / Bellman-Ford /

该算法将以最多log（最大可能的边缘成本）运行DFS / BFS。

该算法将如下工作：

lo = 0, hi = largest cost from any edge from a graph
mid = dummy_value

while ( lo < hi ):
    mid = (lo + hi) / 2
    check if there is a path from source to destination using only edges with cost <= mid
    if there is a path:
        hi = mid
    else:
        lo = mid + 1

return mid

使用DSU的解决方案具有更好的运行时复杂性，但这引入了对答案进行二元搜索的想法，这是解决问题的经典理念。在某些问题中，做DSU是不可能的。