Widest path problem とは

グラフアルゴリズムでは、最も広いパス問題は、重み付きグラフ内の2つの指定された頂点間のパスを見つけ、パス内の最小ウェイトエッジの重みを最大にする問題です。最も広いパス問題は、ボトルネック最短パス問題または最大容量パス問題とも呼ばれます。パスの長さの代わりにボトルネックの距離を使用するように変更することで、最短パスのアルゴリズムを適用して最も広いパスを計算することが可能です。しかし、多くの場合、さらに高速なアルゴリズムが可能です。
例えば、エッジの重みが2つのルータ間の接続の帯域幅を表すインターネットにおけるルータ間の接続を表すグラフにおいて、最も広い経路の問題は、2つのインターネット間のエンドツーエンド経路を見つける問題である可能な最大帯域幅を持つノード。このパスの最小エッジ重みは、パスの容量または帯域幅と呼ばれます。広域経路問題は、ネットワークルーティングにおけるアプリケーションと同様に、多方向選挙の優勝者を決定するためのSchulzeメソッドの重要なコンポーネントでもあり、デジタル合成、代謝経路分析、最大フローの計算に適用されています。
密接に関連する問題、ミニマックス経路の問題は、そのエッジの最大重みを最小にする経路を求める。輸送計画を含むアプリケーションがあります。最も広い経路問題のアルゴリズムは、アルゴリズムによって実行されるすべての重み比較の意味を逆にすることによって、または等価的にすべてのエッジ重みをその否定によって置き換えることによって、ミニマックス経路問題のアルゴリズムに変換することができる。