ネットワーク内の単一のパスに沿って最大帯域幅を見つける

Question

加重指示グラフが与えられた場合、重みが個々のリンク帯域幅に対応する、どのノードが最高のダウンロード（またはアップロード）容量を持っているかを教えてくれるアルゴリズムを検索しようとしています。私は、最大の流れの問題とエドモンド・カープアルゴリズムを見ました。私の質問は次のとおりです。

1. Edmond-Karpは、パスのいずれかが使用された場合、ソースからシンクまで（シンクで）どれだけのスループットを取得できるかを教えてくれます。正しい？
2. エドモンドカープは、どのパスが最大の流れを与えることができるかを教えてくれません。正しい？

Answer 1

質問2の非常に簡単なアプローチは次のとおりです。容量でエッジを並べ替えます。容量が最も低いエッジを削除し、$ s $から$ t $までのパスがまだあるかどうかを確認します。ある場合は、2番目に低い容量で端を移動します。

ある時点で、容量$ c $のエッジを削除することにより、$ t $から$ s $を切断します。これで、$ c $が$ s $から$ t $から1つのパスの最大容量であることがわかっています。

このアルゴリズムは、時間$ o（m^2）$の時間がかかります。これは、接続チェックを時間$ o（m）$で行うことができ、せいぜい各エッジを1回削除できるためです。

これで、この縮小グラフで$ s $-$ t $のパスを見つけることにより、最大容量の実際のパス（多くの可能性があるかもしれません）を見つけることができます。

ノード容量を検討するときは、グラフを変更してそれをサポートすることを忘れないでください。

Answer 2

パスが与えられた場合、それに沿って繰り返して、容量が最も高いノードを見つけます。

コメントから蒸留されているので、このより興味深い質問を考えてみましょう。

限られた帯域幅でリンク$ e $に接続されたノード$ n $のネットワークが与えられた場合、$ b：e to mathbb {n} $、$ s $から$ t $のパスを最大帯域で見つけます。

言い換えれば、あなたは$ s $-$ t $ -path $ p =（s、v_1、 dots、v_k、t）$を探しています。

$ qquad displaystyle b（p）：= min {b（s、v_1）、b（v_k、t）} cup {b（v_i、v_ {i+1} mid i = 1 、 dots、k-1 } $

すべての$ s $-$ t $ -pathsの中で。

サイクルが$ b $とパスバンドを変更しないことは注目に値します。そのため、この点で最小限のパスに制限できます。 木々に及ぶ.

さらに、すべての$ b $ -optimalパスの中で、最短パスの問題から知っているサブパスオプティマリティプロパティを持っている（少なくとも）サブパスオプティマリティプロパティがあることに注意してください。彼らは接続します）。それはすべての$ b $ $ -optimalパス¹には保持されませんが、それは問題ではありません：私たちが知っておくべきことはそこにあるということです は $ b $ -optimalパスの連結から構築できるA $ b $ -optimalパス。したがって、そのような（部分的な）パスのみを考慮することを制限することができます。

これにより、と同様の貪欲な戦略のための十分な正当性を収集しました Primのアルゴリズム: ：$ s $から始めて、既に訪問したノード（すでに訪問された2つのノードを接続していない）にインシデントされているエッジの最大帯域のエッジを連続的に選択します。これにより、$ b $ -optimalパスのみが発見され、$ b $ -optimal $ s $-$ t $ -path（$ t $が$ s $から到達可能な場合）。

これは、$ o（| n |^2）$の時間で実行されます。

---

1. このグラフを考えてみましょう：

   
   ^[ソース]

   すべての$ s $-$ t $ -pathsは最適ですが、下位ノードを介して進むものは最適ではないサブパスを持っています。

Answer 3

これは、dijkstraに簡単な変更を行うことで、O（vlogv + e）時間で実行できます

key（node n）= sからnへの単一パス最大流量

更新キー：pがnキー（n）= min（key（p）、edge（p、n）の前身の場合

これは、すべてのパスの場合ですp =（s、a_2、... a_m-1、a_m）

パスP = min（容量（a_m-1、a_m）の最大流量、p- {a_m}の最大流量）

これは、x = max（max flow）への単一パスmax flowがsからxへのすべてのパスpの流れで動作します。