1. 概要

このチュートリアルでは、グラフ理論における最大-最小パス容量の問題について説明します。 それが何であるか、それを解決する方法、および解決策がダイクストラのとどのように異なるかを定義します。

2. 問題の定義

最大-最小パス容量の問題は、重み付きグラフを扱います。

各エッジの重みは、そのエッジの容量を表すと見なされます。 私たちのタスクは、ソースノードから始まり、グラフ内のゴールノードで終わるパスを見つけることです。 パスの容量が最も少ないエッジがそのパスの容量を形成します。

からへのすべてのパスの中で、最大容量のパスを見つけます。

実際の例として、グラフが各パイプが1秒間に供給できる水の容量を表していると仮定します。 明らかに、私たちは毎秒最大量の水を供給することができるパスを探しています、そして私たちはパス内の最小のパイプよりも速くそれを供給することはできません。

3. 例

次の例を見てください。 ソースノードをと見なし、ゴールノードをと見なします。

グラフの例から、ノードとを接続する複数のパスがあることがわかります。 次の表に、さまざまなパスとその容量を示します。

すべてのパスの中で、パス番号3の容量が最大で4です。 したがって、指定されたグラフの最大-最小容量は4になります。

4. アルゴリズム

この問題を解決するために、ダイクストラのアルゴリズムの修正バージョンを使用します。

4.1. ダイクストラのアルゴリズムとの違い

この問題の擬似コードは、主に次の変更を加えたダイクストラのアルゴリズムから派生しています。

  • 距離配列の代わりに、という配列があります。 この配列は、それぞれの最大容量を格納します。 ノードの最大容量とは、このノードからのすべてのパスの最大-最小容量を意味します。
  • ダイクストラのアルゴリズムでは、各ノードの距離を。で初期化します。
    • のスロットについては、これを実行します。これは、ソースノードがそれ自体に対して無制限の容量を持っていることを示しています。
    • ただし、残りのスロットについては、最悪の場合に対応して、配列をで初期化します。
  • この問題では、あるノードの隣接ノードを訪問する場合、隣接ノードの容量を更新する概念は、ダイクストラのアルゴリズムの概念とは異なります。 この場合、は、 各隣接ノードの容量を、前の値の中で最大値、この隣接ノードに到達したノードの容量、およびエッジの容量で更新します。ちょうど交差した。 また、使用するデータ構造内のこの隣接ノードの容量を更新する必要があります。
  • 各ステップでは、コストが最も低いノードを選択するのではなく、容量が最も大きいノードを選択します。

このアルゴリズムの最適性の証明は、常に最大容量のノードを処理することです。 したがって、ゴールノードに到達すると、データ構造内の残りのすべてのノードの容量が小さくなる必要があります。 したがって、検出されたパスは、最大-最小容量を持つパスになります。

4.2. 擬似コード

それでは、擬似コードでアルゴリズムを確認しましょう。

まず、配列を。で初期化します。 また、ノードごとに、最大パス容量のノードに到達するためのノードを格納する配列を初期化します。

次に、ソースノードの容量をで初期化し、すべてのノードをに追加します。 目的は、これまでのところ最大容量のノードをすばやく見つけることです。 また、関数を介して一部のノードの容量の更新をサポートする必要があります。 このために、容量に基づいて降順でソートされた容量を持つノードを格納するsetを使用できます。

各ステップで、関数を使用して最大パス容量のノードを抽出します。 抽出されたノードの容量がに等しい場合、ノード内の残りのすべてのノードに到達することはできません。 したがって、それ以上のノードの処理を停止することができます。

それ以外の場合は、ノードのすべてのネイバーを反復処理します。 ネイバーごとに、新しい容量を計算します。 新しい容量は、ノードの容量ととの間のエッジの容量の間の最小値です。 したがって、パスに沿って最小容量を採用しました。

その後、ノードの新しい容量と古い容量を比較します。 新しい容量の方が良い場合は、ノードの情報を新しい容量で更新します。 ノードの情報の更新には、その容量の更新、ノードの値の更新、およびこのノードのオブジェクトを削除して新しいパス容量で再度追加する関数の使用が含まれます。

最後に、計算された容量であるを返します。

このアルゴリズムは、ダイクストラのアルゴリズムと同様に、の複雑さを持つように実装できます。ここで、はグラフ内のエッジの数であり、は頂点の数です。

4.3. パスを見つける

アレイを使用して、必要なパスを復元します。 アルゴリズムを見てみましょう：

アルゴリズムは単純です。 ノードから始めます。 各ステップで、現在のノードをパスに追加します。 また、関数で計算された配列を使用して、前のノードに1ステップ戻ります。

ノードの前のノードはに等しいので、値に達したら戻るのをやめることができます。

このアルゴリズムの複雑さ（findMaxMin関数なし）はです。ここで、はグラフ内の頂点の総数です。

5. 結論

このチュートリアルでは、グラフ問題の最大-最小容量を示しました。 まず、問題を定義しました。 次に、概念をよりよく説明する例を示しました。

その後、私たちのアルゴリズムとダイクストラのアルゴリズムの主な違いを強調しました。

最後に、アルゴリズムを示しました。