graph - 所有路径之间权重最低的最重边

Question

给定一个具有 n 个顶点、间接加权、没有负环和两个节点 s,t 的图 - 找到从 s 到 t 的路径，该路径中最重的边在从 s 到 t 的所有路径之间具有最轻的权重。

我考虑的一种解决方案是从 s 运行 BFS，在 s 到 t 之间找到一些路径，保存路径中最重的边缘，删除它，最多执行 |E| 次。复杂度为 O(|V| + |E|)*E)。我正在寻找另一种可能涉及网络流量的解决方案。

谢谢。

Answer 1

一个简单的想法是删除所有边，然后按升序将它们添加回来，直到 s 和 t 连接（您可以通过跟踪每个节点属于每个迭代的岛来快速完成）。最后，做 BFS。