graph - 沿路径的最小边权重

Question

如何沿着任意顶点之间的所有可能路径找到一组最小边权重的最大值(u,v)？

我在考虑修改 Floyd-Warshall？

i.e. Path 1: s - a - b - c - d - t with weights 1 - 5 - 6 - 10 - 9

最小边权重为 1

Path 2: s - x - y - z - w - t with weights 3 - 9 - 8 - 6 - 7

最小边权重为 3

因此结果是max(1, 3) = 3

Answer 1

是的，对 Floyd-Warshall 的修改会起作用 - 您将跟踪最大路径“宽度”，而不是最短路径长度。

如果您只对两个顶点感兴趣，您可以采取更简单的方法：从一个空图开始，然后添加按其权重排序的边（从高到低）。当有问题的节点连接时，添加的最后一条边会为您提供最大的“宽度”。正确完成（即使用不相交集来检查连通性），这将比 Floyd-Warshall 更快。

注意：我只考虑正权重。