沿路径的最小边权重

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

注：我只考虑正面权重。