パスに沿った最小エッジ重み

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の修正が機能します - 最短パス長ではなく、最大パス "width"を追跡します。

2つの頂点にのみ興味がある場合は、より簡単なアプローチを取ります。問題のノードが接続されている場合、追加された最後のエッジは最大限の "width"を与えます。正しく行われた（すなわち、接続されているセットを使用して、接続されていることを確認する）、これは早くフロイドウォーシャルになるでしょう。

注：私は肯定的な重みを考慮しています。