graph - パスに沿った最小エッジウェイト

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の変更は機能します。最短パスの長さの代わりに、最大パスの「幅」を追跡します。

2つの頂点のみに関心がある場合は、より簡単なアプローチをとることができます。空のグラフから始めて、重みの順に（高いものから低いものへ）エッジを追加します。問題のノードが接続されると、最後に追加されたエッジによって最大の「幅」が得られます。適切に行われると（つまり、接続性をチェックするために互いに素なセットを使用する）、これはFloyd-Warshallよりも高速になります。

注：私は正の重みのみを考慮しています。