algorithm - 图 - 从 s 到 t 的路径，具有最小的单个边长

Question

我想知道是否可以修改 Dijkstra 的算法以找到两个节点之间的路径，其中路径中所有边长的最大值最小。

即它更喜欢边长为 1,3,5,9 的路径，而不是单边长 10 的路径，因为 max(1,3,5,9) < max(10)

Answer 1

是的，这可以使用 Dijkstra 算法来完成

提示：在每个节点 u 处，存储最小的权重 w，这样就存在一条从 s 到 u 的访问顶点的路径，其最大权重为 w。考虑在访问新顶点时修改松弛条件以满足上述条件。

Answer 2

还记得 d(u) 何时被 d(v)+c(u,v) 更新吗？现在，您只需将 d(u) 更新为 max(d(v),c(u,v)) 即可。

另一种解决方案是对结果进行二进制搜索。对于给定的上限，您可以删除违反该上限的边，然后使用 DFS/BFS 检查两个节点 s & t 之间是否仍有路径。因此，现在您可以尝试不同的上限以使用二分搜索找到最严格的上限。