沿路径的最小边重量

Question

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

我在想修改弗洛伊德-沃夏尔？

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更快。

注:我只考虑正权重。