恢复时间最短的路径

Question

问题描述如下：

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

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

我们有三个数组：

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

Example:

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

where the recovery time of the connection between nodes 1 and 2 is 1, etc..

The optimal path from 1 to n = 4 is 1-2-3-4, since the longest recovery time on this path is 5, in comparison to the path 1-2-4, where the longest recovery time is 10.

这里重要的是要注意，只有每条路径上最长的恢复时间才是最重要的，即路径的“长度”不是等待时间的总和，而是最长时间的长度必须等待两个节点之间的连接恢复。每个恢复时间都是从t = 0开始计算的，所以恢复时间是独立的，顺序无所谓。

所以我们要做的就是在每条路径的最大恢复时间中找到恢复时间最短的路径，并且return那个时间。

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

Answer 1

使用 DSU (https://en.wikipedia.org/wiki/Disjoint-set_data_structure) 很容易：

按权重对所有边进行排序，递增
遍历边，如果节点u和v在不同的不相交集合中，则将它们合并为一个不相交集合
如果合并后节点1和N在同一个集合中，asnwer是当前边的权重，我们可以跳出循环。

复杂度：O(E log E + V log V)

Answer 2

DSU 是最漂亮的解决方案，正如 Photon 所描述的那样。

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

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

算法的工作原理如下：

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 是不可能的。

恢复时间最短的路径

Path with the shortest recovery time

algorithm

graph

dijkstra

shortest-path

bellman-ford