2012-05-20 60 views
0

如何找到任意頂點之間沿所有可能路徑的最小邊權重的最大值(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

回答

0

是,弗洛伊德-沃肖爾的變形將工作 - 代替最短路徑長度,您將跟蹤最大路徑「寬度」。

如果你只對兩個頂點感興趣,你可以採取一個更簡單的方法:從一個空圖開始,並添加按其權重排序的邊(從高到低)。當有問題的節點連接時,最後添加的邊緣會爲您提供最大的「寬度」。正確完成(即使用不相交集來檢查連通性),那麼Floyd-Warshall會更快。

注:我只考慮正面權重。