プッシュ・リラベル最大フローアルゴリズム

数理最適化において、プッシュ・リラベルアルゴリズム（別名、プリフロー・プッシュアルゴリズム）は、フローネットワークにおける最大フローを計算するアルゴリズムです。「プッシュ・リラベル」という名前は、このアルゴリズムで使用される2つの基本操作に由来します。このアルゴリズムは、実行中ずっと「プリフロー」を維持し、リラベル操作によって維持される許容ネットワークのガイダンスの下、プッシュ操作を使用して隣接するノード間でフローを局所的に移動させることで、徐々に最大フローに変換します。これに対し、フォード・ファルカーソンアルゴリズムは、ソースからシンクまでパスに沿ってフローを送るグローバルな拡張を実行します。^[¹^]

プッシュリラベルアルゴリズムは、最も効率的な最大フローアルゴリズムの 1 つと考えられています。汎用アルゴリズムは、 $O$ $($ $V$ $2$ $E$ $)$ という強力な多項式時間計算量を持ち、漸近的には $O$ $($ $VE$ $2$ $)$ の Edmonds–Karp アルゴリズムよりも効率的です。^[²^]アルゴリズムの特定のバリアントは、さらに低い時間計算量を実現します。最高ラベルノード選択ルールに基づくバリアントは、 $O$ $($ $V$ $2$ $\sqrt$ $E$ $)$ の時間計算量を持ち、一般的に最大フローアルゴリズムのベンチマークと見なされています。^[³^]^[⁴^]動的ツリーを使用すると、サブ3次 $O$ $($ $VE$ $log($ $V$ $2$ $/$ $E$ $))$ の時間計算量を実現できますが、^[²^]実際には効率が劣ります。

プッシュリラベルアルゴリズムは、最小コストフローを計算するように拡張されています。^{[ 5 ]}距離ラベルのアイデアは、より効率的な拡張パスアルゴリズムにつながり、それがプッシュリラベルアルゴリズムに組み込むことで、さらに高い経験的パフォーマンスを持つバリアントを作成できます。^{[ 4 ]}^{[ 6 ]}

歴史

プリフローとは、頂点に流入する総量が、そこから流出する総量よりも大きい可能性があるフローであり、アルゴリズムによって単一のアーク上のフローを変更できる。^{[ 7 ]}このアイデアは元々アレクサンダー・V・カルザノフによって考案され、1974年にソビエト数学ドクラディ15で発表された。このプリフローアルゴリズムもプッシュ操作を使用していたが、ラベル付けシステムの代わりに補助ネットワーク内の距離を使用してフローをプッシュする場所を決定していた。^{[ 2 ]}^{[ 8 ]}

プッシュリラベルアルゴリズムは、Andrew V. GoldbergとRobert Tarjanによって設計されました。このアルゴリズムは、1986 年 11 月に STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computing で最初に発表され、その後 1988 年 10 月に Journal of the ACM の記事として正式に発表されました。両方の論文では、 $O (V 2 E)$ で終了するアルゴリズムの汎用形式と、 $O (V 3)$ の逐次実装、動的ツリーを使用した $O (VE log(V 2 / E))の実装、および並列/分散実装の詳細が説明されています。$ ^{[ 2 ]}^{[ 7 ]}^{[ 9}^]で説明されているように、 Goldberg–Tarjan は、 ^Yossi Shiloach とUzi Vishkinの並列最大フローアルゴリズムに距離ラベルを組み込むことによって距離ラベルを導入しました。^[¹⁰^]

概念

定義と表記法

させて：

$G = (V, E)は$ 容量関数 $c$ $:$ $V$ $\times$ $V$ $\to ℝ$ $\infty$ を持つネットワークとする。
$F = (G, c, s, t)$ はフローネットワークであり、 $s \in V$ および $t \in V$ (s ≠ t) はそれぞれ選択されたソース頂点およびシンク頂点である。
$f : V \times V \to ℝは$ $F$ における前流を表す。
$x f : V \to ℝ は、流れ$ $f$ に関する超過関数を表し $、 x$ $f$ $($ $u$ $) = Σ$ $v$ $\in$ $V$ $f$ $($ $v$ $,$ $u$ $) - Σ$ $v$ $\in$ $V$ $f$ $($ $u$ $,$ $v$ $)$ で定義されます。
$c f : V \times V \to ℝ \infty は$ $、流量f$ に関する残余容量関数を表し、 $c$ $f$ $($ $e$ $) =$ $c$ $($ $e$ $) -$ $f$ $($ $e$ $)$ で定義されます。
$E f \subset Eは$ $f < c$ となる辺である。

そして

$G f (V, E f)は、流れ$ $f$ に関する $G$ の残余ネットワークを表します。

プッシュ・リラベルアルゴリズムは、ノード上の距離ラベル（高さ）を利用してプッシュ操作で選択するアークを決定する、非負整数の有効なラベル付け関数を使用します。このラベル付け関数は、 $𝓁$ $:$ $V$ $\to ℕ$ で表されます。この関数が有効とみなされるには、次の条件を満たす必要があります。

有効なラベル表示：

𝓁(u) \leq 𝓁(v) + 1

がすべての

(u, v) \in E fに対して成り立つ

ソース条件：

𝓁(s) = | V |

シンクの保全：

𝓁(t) = 0

$このアルゴリズムでは、 s$ と $t$ のラベル値は固定されています。𝓁 $(u)は、$ $uから$ $t$ に到達可能な場合、 $G$ $f$ における $uから$ $t$ への重みなし距離の下限です。u $が$ $t$ から切断されている場合、 $𝓁($ $u$ $) - |$ $V$ $|は$ $uから$ $s$ への重みなし距離の下限です。結果として、有効なラベル付け関数が存在する場合、そのようなパスは $|$ $V$ $| - 1$ より長くなることはないため、 $G$ $f$ $にはs$ $-$ $t$ パスは存在しません。

弧 $(u, v) \in E f$ $は、 𝓁($ $u$ $) = 𝓁($ $v$ $) + 1$ の場合に許容可能である という。許容ネットワーク $G̃$ $f$ $($ $V$ $,$ $Ẽ$ $f$ $)は、許容可能な弧$ $e$ $\in$ $E$ $f$ の集合から構成される。許容ネットワークは非巡回的である。

固定されたフロー $f$ に対して、頂点 $v \notin {s, t} は、$ $f$ に関して正の超過を持つ場合、すなわち $x$ $f$ $($ $u$ $) > 0 である場合に$ アクティブと呼ばれます。

業務

初期化

このアルゴリズムは、まず残余グラフを作成し、プリフロー値をゼロに初期化し、ソースから出る残余アーク $(s, v)に対して一連の飽和プッシュ操作を実行します。ここで、$ $v ∈ V \ { s }$ です。同様に、ラベルは初期化され、ソースのラベルはグラフ内のノード数 $𝓁(s) = | V |$ となり、その他のすべてのノードにはラベル 0 が割り当てられます。初期化が完了すると、アルゴリズムは適用可能な操作がなくなるまで、アクティブなノードに対してプッシュ操作またはリラベル操作を繰り返し実行します。

押す

The push operation applies on an admissible out-arc $(u, v)$ of an active node $u$ in $G f$ . It moves $min{x f (u), c f (u, v)}$ units of flow from $u$ to $v$ .

push(u, v): assert x_f[u] > 0 and 𝓁[u] == 𝓁[v] + 1 Δ = min(x_f[u], c[u][v] - f[u][v]) f[u][v] += Δ f[v][u] -= Δ x_f[u] -= Δ x_f[v] += Δ

A push operation that causes $f (u, v)$ to reach $c (u, v)$ is called a saturating push since it uses up all the available capacity of the residual arc. Otherwise, all of the excess at the node is pushed across the residual arc. This is called an unsaturating or non-saturating push.

Relabel

The relabel operation applies on an active node $u$ which is neither the source nor the sink without any admissible out-arcs in $G f$ . It modifies $𝓁(u)$ to be the minimum value such that an admissible out-arc is created. Note that this always increases $𝓁(u)$ and never creates a steep arc, which is an arc $(u, v)$ such that $c f (u, v) > 0$ , and $𝓁(u) > 𝓁(v) + 1$ .

relabel(u): assert x_f[u] > 0 and 𝓁[u] <= 𝓁[v] for all v such that c_f[u][v] > 0 𝓁[u] = 1 + min(𝓁[v] for all v such that c_f[u][v] > 0)

Effects of push and relabel

After a push or relabel operation, $𝓁$ remains a valid labeling function with respect to $f$ .

許容弧 $(u, v)$ に対するプッシュ操作では、弧 $(v, u)を$ $E f$ に追加できます。ここで $𝓁(v) = 𝓁(u) - 1 \leq 𝓁(u) + 1$ です。また、弧 $(u, v)を$ $E f$ から削除することもできます。この場合、制約 $𝓁(u) \leq 𝓁(v) + 1 が$ 実質的に削除されます。

$ノードu$ に対するラベル変更操作が $𝓁(u)$ の妥当性を維持することを確認するには、 $G$ $f$ 内のuのアウトアークについては定義により自明に保証されていることに注目してください。G $f$ 内の $u$ のインアークについては、増加した $𝓁($ $u$ $)$ $は$ 制約を緩やかに満たすだけで、違反することはありません。

汎用プッシュリラベルアルゴリズム

汎用プッシュ・リラベルアルゴリズムは概念実証のみに使用され、プッシュおよびリラベル操作のアクティブノードを選択する方法に関する実装の詳細は含まれていません。この汎用バージョンのアルゴリズムは $O (V 2 E)$ で終了します。

$𝓁(s) = | V |$ 、 $𝓁(t) = 0$ であり、 $G$ $f$ には $| V | - 1$ より長いパスが存在しないため、 $𝓁($ $s$ $)$ が有効なラベル付け条件を満たすためには、 $s は$ $t$ から切り離されている必要があります。初期化時に、アルゴリズムはこの要件を満たすために、 $s$ のすべてのアウトアークを飽和させるプリフロー $f$ を作成します。その後、 $𝓁($ $v$ $) = 0は、すべての$ $v$ $\in$ $V$ $\ {$ $s$ $,$ $t$ $}$ に対して自明に有効です。初期化後、アルゴリズムは適用可能なプッシュまたはリラベル操作を繰り返し実行し、そのような操作がなくなると、プリフローは最大フローに変換されます。

generic-push-relabel(G, c, s, t): s のすべての外弧を飽和させるプリフロー f を作成します 𝓁[s] = |V| とし、𝓁[v] = 0 とする。すべての v ∈ V \ {s} について 、適用可能なプッシュまたはリラベル操作が存在する間、 操作を実行する。

正確さ

The algorithm maintains the condition that $𝓁$ is a valid labeling during its execution. This can be proven true by examining the effects of the push and relabel operations on the label function $𝓁$ . The relabel operation increases the label value by the associated minimum plus one which will always satisfy the $𝓁(u) \leq 𝓁(v) + 1$ constraint. The push operation can send flow from $u$ to $v$ if $𝓁(u) = 𝓁(v) + 1$ . This may add $(v, u)$ to $G f$ and may delete $(u, v)$ from $G f$ . The addition of $(v, u)$ to $G f$ will not affect the valid labeling since $𝓁(v) = 𝓁(u) - 1$ . The deletion of $(u, v)$ from $G f$ removes the corresponding constraint since the valid labeling property $𝓁(u) \leq 𝓁(v) + 1$ only applies to residual arcs in $G f$ .^[7]

If a preflow $f$ and a valid labeling $𝓁$ for $f$ exists then there is no augmenting path from $s$ to $t$ in the residual graph $G f$ . This can be proven by contradiction based on inequalities which arise in the labeling function when supposing that an augmenting path does exist. If the algorithm terminates, then all nodes in $V \ {s, t}$ are not active. This means all $v ∈ V \ {s, t}$ have no excess flow, and with no excess the preflow $f$ obeys the flow conservation constraint and can be considered a normal flow. This flow is the maximum flow according to the max-flow min-cut theorem since there is no augmenting path from $s$ to $t$ .^[7]

Therefore, the algorithm will return the maximum flow upon termination.

Time complexity

アルゴリズムの時間計算量を制限するためには、メインループ内で発生するプッシュ操作とリラベル操作の数を分析する必要があります。リラベル操作、飽和プッシュ操作、非飽和プッシュ操作の数はそれぞれ個別に分析されます。

このアルゴリズムでは、ラベル付けの変更操作は最大で $(2| V | - 1)(| V | - 2) < 2| V | 2$ 回実行できます。これは、任意のノードuのラベル付け $𝓁(u)$ の値は決して減少せず、すべてのノードの最大ラベル値は最大で $2|$ $V$ $| - 1$ であるためです。つまり、ラベル付けの変更操作は、すべてのノード $V$ $\ {$ $s$ $,$ $t$ $}$ (つまり $|$ $V$ $| - 2 ) に対して、潜在的に$ $2|$ $V$ $| - 1$ 回実行される可能性があります。これにより、ラベル付けの変更操作の上限は $O$ $($ $V$ $2$ $)となります。$

許容弧 $(u, v)に対する飽和プッシュは、$ $G f$ から弧を削除します。別の飽和プッシュのために弧を $G f$ $に再挿入するには、まずv のラベルを変更し、次に弧$ $(v, u)$ に対するプッシュを行い、その後 $u の$ ラベルを変更する必要があります。この過程で、 $𝓁(u) は$ 少なくとも 2 増加します。したがって、 $($ $u$ $,$ $v$ $)$ に対する飽和プッシュは $O (V)$ 回あり、飽和プッシュの総数は最大で $2|$ $V$ $||$ $E$ $|$ です。これにより、飽和プッシュ操作の時間制限は $O$ $($ $VE$ $)となります。$

非飽和プッシュの数を制限するには、ポテンシャル引数を使用します。ポテンシャル関数 $Φ = Σ [u \in V \land x f (u) > 0] 𝓁(u)$ (つまり、 $Φ$ はすべてのアクティブノードのラベルの合計) を使用します。Φ は最初は 0 であり、アルゴリズムの実行中ずっと非負であることは明らかです $。$ $リラベル$ と飽和プッシュの両方で $Φを増やすことができます。ただし、アルゴリズムの実行終了時にはアクティブなノードが残っていないため、終了時の$ $Φ$ の値は0 でなければなりません。これは、アルゴリズムの実行中に、非飽和プッシュがリラベル操作と飽和プッシュ操作の差を埋めなければ、 $Φ は$ 0 の値で終了しないことを意味します。リラベル操作は、 $Φ を$ 最大で $(2| V | - 1)(| V | - 2)$ だけ増やすことができます。 $(u, v)$ に対する飽和プッシュは、プッシュ前に $v$ が非アクティブだった場合、vをアクティブにし、 $Φ を$ 最大で $2| V | - 1だけ増加させます。したがって、すべての飽和プッシュ操作による$ $Φ$ への合計寄与は最大で $(2| V | - 1)(2| V || E |)です。$ $(u, v)$ に対する非飽和プッシュは常に $u を$ 非アクティブにしますが、飽和プッシュと同様に $v を$ アクティブにすることもできます。結果として、 $Φ を$ 少なくとも $𝓁(u) - 𝓁(v) = 1 だけ$ 減少させます。リラベルと飽和プッシュは $Φ$ を増加させるため、非飽和プッシュの総数は $(2| V | - 1)(| V | - 2) + (2| V | - 1)(2| V || E |) \leq 4| V | 2 | E |$ の差を埋める必要があります。これにより $、$ 非飽和プッシュ操作の時間制限は $O(V2E)$ $となります。$

要約すると、このアルゴリズムは $O (V 2)$ 回のリラベル、 $O (VE)$ 回の飽和プッシュ、および $O (V 2 E)回の非飽和プッシュを実行します。データ構造は、適用可能な操作を選択して$ $O (1)$ 時間で実行するように設計できます。したがって、このアルゴリズムの時間計算量は $O (V 2 E)$ です。^{[ 1 ]}^{[ 7 ]}

例

以下は、上記で定義した汎用プッシュリラベルアルゴリズムを、次の単純なネットワークフローグラフ図に対して実行した例です。

初期フローネットワークグラフ

最終的な最大フローネットワークグラフ

この例では、hとe の値は、それぞれアルゴリズム実行中のノードのラベル $𝓁$ と超過 $x f$ を表します。例中の各残差グラフには、容量がゼロより大きい残差アークのみが含まれます。各残差グラフには、perform 操作ループの複数回の反復が含まれる場合があります。

この例（ただし初期流量は0）は、ここで対話的に実行できます。

実践的な実装

一般的なプッシュ・リラベルアルゴリズムの時間計算量はO(V2E)ですが $、$ 適切なプッシュ操作とリラベル操作を選択する際に適切なルールを適用することで、効率的な実装ではO(V3)以下の時間計算量を実現できます $。経験的な$ $パフォーマンスは、$ $ヒューリスティック$ $によって$ $さらに$ 向上させることができます。

「電流アーク」データ構造と放電操作

「カレントアーク」データ構造は、フローネットワーク内のノードの入ノードと出ノードを静的な循環順序で走査するためのメカニズムです。ノードに対して単方向連結リストが作成されている場合、データ構造は、リストを順に走査し、末尾に達したら先頭に戻るポインターという単純なものになります。

「電流アーク」データ構造に基づいて、放電操作を定義できます。放電操作はアクティブなノードに適用され、ノードが非アクティブになるまで繰り返しフローをノードから押し出し、その過程で許容可能なアークを作成するために必要に応じてノードのラベルを変更します。

discharge(u): while x _f [u] > 0 do if current-arc[u] has run off the end of neighbors[u] then relabel(u) 巻き戻し電流アーク[u] そうでなければ、 (u, v) = current-arc[u] とする。 (u, v) が許容可能であれば、 push(u, v) current-arc[u]がuの次の隣接ノードを指すようにします。

次に押し進めるべき許容可能なエッジを見つけるには $O(1)$ 償却複雑度。現在のアークポインタは、現在の隣接ノードへのエッジが飽和または非許容の場合にのみ次の隣接ノードに移動し、これらの2つのプロパティはアクティブノードが変化するまで変更できません。 $u$ ラベルが再付けられます。したがって、ポインタが走ったときには、許容される飽和していないエッジはなく、アクティブノードのラベルを再付ける必要があります。 $u$ ポインターを移動したので $O(V)$ 回数は $O(V)$ ラベル付け変更操作。^{[ 7 ]}

アクティブノード選択ルール

放電操作の定義により、プッシュ・リラベルアルゴリズムは、放電するアクティブノードを繰り返し選択する操作に簡略化されます。選択ルールによって、アルゴリズムの時間計算量は異なります。簡潔にするため、以下の説明ではノードを指す際に $s$ と $tは省略します。$

FIFO選択ルール

FIFOプッシュリラベルアルゴリズム^[²^]は、アクティブノードをキューに整理します。初期のアクティブノードは任意の順序で挿入できます。このアルゴリズムは、常にキューの先頭にあるノードを放電のために削除します。非アクティブノードがアクティブになると、キューの末尾に追加されます。

このアルゴリズムの時間計算量は $O$ ( $V3) です。$

ラベルを前面に再配置する選択ルール

リラベル・トゥ・フロント・プッシュ・リラベル・アルゴリズム^{[ 1 ]}は、すべてのノードをリンクリストに整理し、リストが許容ネットワークに関してトポロジカルにソートされているという不変条件を維持します。このアルゴリズムはリストを前から後ろにスキャンし、現在のノードがアクティブな場合は、そのノードに対して放電操作を実行します。ノードがリラベルされた場合、そのノードはリストの先頭に移動され、スキャンは先頭から再開されます。

このアルゴリズムの時間計算量は $O$ ( $V3) です。$

最高位のラベル選択ルール

最高ラベルプッシュ再ラベルアルゴリズム^{[ 11 ]}は、すべてのノードをラベルでインデックス付けされたバケットに整理します。このアルゴリズムは常に、最大のラベルを持つアクティブなノードを選択して放電します。

アルゴリズムは $O(V^{2}{\sqrt {E}})$ 時間計算量。代わりに最小ラベル選択ルールを使用すると、時間計算量は $O (V 2 E)$ になります。^{[ 3 ]}

実装技術

上記の一般的なプッシュリラベルアルゴリズムの説明では、最初に $s$ と $t$ 以外の各ノードuに対して $𝓁(u)$ をゼロに設定していますが、正確なラベルを計算するには、 $t$ から後方幅優先探索を実行する方が望ましいです。^[²^]

$このアルゴリズムは通常、2 つのフェーズに分けられます。フェーズ 1 では、ラベルがn$ 未満のアクティブノードのみを解放することで最大プリフローを計算します。フェーズ 2 では、 $t$ に到達できない余剰フローを $s$ に返すことで、最大プリフローを最大フローに変換します。フェーズ 2 はプッシュ操作とリラベル操作の順序に関係なく $O (VE) の$ 時間計算量を持つことが示されており、したがってフェーズ 1 に支配されます。あるいは、フロー分解を使用して実装することもできます。^{[ 9 ]}

ヒューリスティックは、アルゴリズムの経験的パフォーマンスを向上させる上で非常に重要です。^{[ 12 ]}よく使用されるヒューリスティックは、ギャップヒューリスティックとグローバル再ラベル付けヒューリスティックの 2 つです。^{[ 2 ]}^{[ 13 ]}ギャップヒューリスティックは、ラベル付け関数のギャップを検出します。0 < 𝓁 ' < | V |のラベルがあり、 $𝓁($ $u$ $) = 𝓁$ $'$ となるノード $u$ が存在しない場合、 $𝓁$ $'$ $< 𝓁($ $u$ $) < |$ $V$ $|$ のノード $uは$ $t$ から切断されており、すぐに $(|$ $V$ $| + 1)$ に再ラベル付けできます。グローバル再ラベル付けヒューリスティックは、 $G$ $f$ 内の $t$ から後方幅優先探索を定期的に実行して、ノードの正確なラベルを計算します。どちらのヒューリスティックも、アルゴリズムのボトルネックであり、動的ツリーの非効率性の原因となる役に立たない再ラベル付け操作をスキップします。^[⁴^]

サンプル実装

C言語による実装

#include <stdlib.h> #include <stdio.h>#define NODES 6 #define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) #define INFINITE 10000000void push ( const int * const * C , int ** F , int * excess , int u , int v ) { int send = MIN ( excess [ u ], C [ u ][ v ] - F [ u ][ v ]); F [ u ][ v ] += send ; F [ v ][ u ] -= send ; excess [ u ] -= send ; excess [ v ] += send ; }void relabel ( const int * const * C , const int * const * F , int * height , int u ) { int v ; int min_height = INFINITE ; for ( v = 0 ; v < NODES ; v ++ ) { if ( C [ u ][ v ] - F [ u ][ v ] > 0 ) { min_height = MIN ( min_height , height [ v ]); height [ u ] = min_height + 1 ; } } };void discharge ( const int * const * C , int ** F , int * excess , int * height , int * seen , int u ) { while ( excess [ u ] > 0 ) { if ( seen [ u ] < NODES ) { int v = seen [ u ]; if (( C [ u ][ v ] - F [ u ][ v ] > 0 ) && ( height [ u ] > height [ v ])) { push ( C , F , excess , u , v ); } else { seen [ u ] += 1 ; } } else { relabel ( C , F , height , u ); seen [ u ] = 0 ; } } }void moveToFront ( int i , int * A ) { int temp = A [ i ]; int n ; for ( n = i ; n > 0 ; n-- ) { A [ n ] = A [ n - 1 ] ; } A [ 0 ] = temp ; }int pushRelabel ( const int * const * C , int ** F , int source , int sink ) { int * excess , * height , * list , * seen , i , p ;excess = ( int * ) calloc ( NODES , sizeof ( int )); height = ( int * ) calloc ( NODES , sizeof ( int )); seen = ( int * ) calloc ( NODES , sizeof ( int ));list = ( int * ) calloc (( NODES - 2 ), sizeof ( int ));for ( i = 0 , p = 0 ; i < NODES ; i ++ ){ if (( i != source ) && ( i != sink )) { list [ p ] = i ; p ++ ; } }height [ source ] = NODES ; excess [ source ] = INFINITE ; for ( i = 0 ; i < NODES ; i ++ ) push ( C , F , excess , source , i );p = 0 ; while ( p < NODES - 2 ) { int u = list [ p ]; int old_height = height [ u ]; discharge ( C , F , excess , height , seen , u ); if ( height [ u ] > old_height ) { moveToFront ( p , list ); p = 0 ; } else { p += 1 ; } } int maxflow = 0 ; for ( i = 0 ; i < NODES ; i ++ ) maxflow += F [ source ][ i ];無料（リスト）無料（表示）；無料（高さ）；無料（超過）；return maxflow ; }void printMatrix ( const int * const * M ) { int i , j ; for ( i = 0 ; i < NODES ; i ++ ) { for ( j = 0 ; j < NODES ; j ++ ) printf ( "%d \t " , M [ i ][ j ]); printf ( " \n " ); } }int main ( void ) { int ** flow , ** capacities , i ; flow = ( int ** ) calloc ( NODES , sizeof ( int * )); capacities = ( int ** ) calloc ( NODES , sizeof ( int * )); for ( i = 0 ; i < NODES ; i ++ ) { flow [ i ] = ( int * ) calloc ( NODES , sizeof ( int )); capacities [ i ] = ( int * ) calloc ( NODES , sizeof ( int )); }// サンプルグラフcapacities [ 0 ][ 1 ] = 2 ; capacities [ 0 ][ 2 ] = 9 ; capacities [ 1 ][ 2 ] = 1 ; capacities [ 1 ][ 3 ] = 0 ; capacities [ 1 ][ 4 ] = 0 ; capacities [ 2 ][ 4 ] = 7 ; capacities [ 3 ][ 5 ] = 7 ; capacities [ 4 ][ 5 ] = 4 ;printf ( "容量: \n " ); printMatrix ( capacities );printf ( "最大流量: \n %d \n " , pushRelabel ( capacities , flow , 0 , 5 ));printf ( "フロー: \n " ); printMatrix ( flow );return 0 ; }

Pythonによる実装

def relabel_to_front ( C , source : int , sink : int ) -> int : """プッシュリラベル最大フローアルゴリズム。""" n = len ( C ) # C は容量行列F = [[ 0 ] * n for _ in range ( n )] # u から v への残余容量は C[u][v] - F[u][v] ですheight = [ 0 ] * n # ノードの高さexcess = [ 0 ] * n # ノードへのフローからノードからのフローを引いた数seen = [ 0 ] * n # 前回のリラベル以降に確認された隣接ノード数 # ノード "queue" nodelist = [ i for i in range ( n ) if i != source and i != sink ]def push ( u , v ): send = min ( excess [ u ], C [ u ][ v ] - F [ u ][ v ]) F [ u ][ v ] += send F [ v ][ u ] -= send excess [ u ] -= send excess [ v ] += senddef relabel ( u ): # プッシュが可能な最小の新しい高さを見つける。# プッシュがそもそも可能な場合。min_height = ∞ for v in range ( n ): if C [ u ][ v ] - F [ u ][ v ] > 0 : min_height = min ( min_height , height [ v ]) height [ u ] = min_height + 1def discharge ( u ): while excess [ u ] > 0 : if seen [ u ] < n : # 次の隣接ノードをチェックv = seen [ u ] if C [ u ][ v ] - F [ u ][ v ] > 0 and height [ u ] > height [ v ]: push ( u , v ) else : seen [ u ] += 1 else : # すべての隣接ノードをチェックしました。ラベルを付け直す必要がありますrelabel ( u ) seen [ u ] = 0height [ source ] = n # ソースからシンクまでの最長パスは n より短い long excess [ source ] = ∞ # ソースの隣接ノードに可能な限り多くのフローを送信するfor v in range ( n ): push ( source , v )p = 0 while p < len ( nodelist ): u = nodelist [ p ] old_height = height [ u ] discharge ( u ) if height [ u ] > old_height : nodelist.insert ( 0 , nodelist.pop ( p )) # リストの先頭に移動p = 0 # リストの先頭から開始else : p + = 1return sum ( F [ source ])

R {base}実装

# (HL) プッシュリラベル最大フローアルゴリズム。# アクティブノード選択ルール: 最高ラベル。# R {base}。push <- function ( u , v ) { d <- min ( excess [ u ], rGraph [ u , v ]) rGraph [ u , v ] <<- rGraph [ u , v ] - d # 前方エッジ、フローなし。rGraph [ v , u ] <<- rGraph [ v , u ] + d # 後方エッジ、以前にルーティングされたフロー、excess [ u ] <<- excess [ u ] - d # 元に戻すことができる。excess [ v ] <<- excess [ v ] + d pushCtr <<- pushCtr + 1L stopifnot ( pushCtr <= nV ^ 2 * sqrt ( nE )) }relabel <- function ( u ) { height [ u ] <<- height [ u ] + 1L relabCtr <<- relabCtr + 1L }# 残余ネットワークグラフを介して頂点 u ≠ {s, t} を解放します。# エッジ (u, v) は、height[u] == height[v] + 1 の場合に許容可能と呼ばれます。discharge <- function ( u ) { neighbours <- which ( rGraph [ u , ] > 0 ) admisible <- neighbours [ which ( height [ u ] == height [ neighbours ] + 1L )] for ( v in admisible ) { push ( u , v ) if ( excess [ u ] == 0 ) break } if ( excess [ u ] > 0 ) relabel ( u ) }# Preflow: 保存制約を緩和したフロー: 流入 ≥ 流出。# 許容エッジ上の余剰フローをシンクに向かって移動します。# グローバルデータ eCap、rGraph、excess、height。1 ベースの頂点 ID でインデックス付けされています。pushRelabel <- function ( source 、sink ) { rGraph <<- eCap # 残余ネットワークグラフ。excess <<- # 流入マイナス流出 (≥ 0)。height <<- rep ( 0L 、nV ) # ラベル (𝓁) 値。height [ source ] <<- nV excess [ source ] <<- Inf relabCtr <<- pushCtr <<- 0L # カウント relabel、プッシュ。# ソースから余剰分をプッシュします。sourceOut <- which ( rGraph [ source , ] > 0 ) for ( i in sourceOut ) push ( source , i )# メインループ。ソースとシンクを除くすべてのノードから、正の超過を持つ最も高いラベルを選択し、放電します。nlist <- setdiff ( seq ( from = 1 , to = nV , by = 1 ), c ( source , sink )) while (( active <- nlist [ which ( excess [ nlist ] > 0 )]) |> length () > 0 ) { u <- active [ which ( height [ active ] == max ( height [ active ]))][ 1 ] discharge ( u ) } # すべての超過流量がシンクに送られました。return ( sum (( eCap - rGraph )[ source , ])) }# トーナメントグラフ、n = 4、最大フロー = n - 1。eCap <- matrix ( 1L , 4 , 4 ); diag ( eCap ) <- 0L colnames ( eCap ) <- c ( "s" , seq ( 2 , length.out = ncol ( eCap ) - 2 ), "t" ) # ソースは 1、シンクは n。print ( list ( "容量マトリックス" = eCap ), max = 1600 )# ソースとシンク間の最大フローを計算します。nV <- ncol ( eCap ) # 頂点。nE <- sum ( eCap > 0 ) # エッジ。system.time ( maxFlow <- pushRelabel ( source = 1L , sink = nV )) print ( paste ( "VE =" , nV , nE , "maxFlow =" , maxFlow )) print ( paste ( "Relabel =" , relabCtr , "Push =" , pushCtr ))# フロー行列が歪対称であることを確認します。# ソースから出るフロー (=1) がシンクに入るフロー (=nV) と等しいことを確認します。flow <- eCap - rGraph stopifnot (((( flow ) == - t ( flow )) |> all ())) stopifnot ( rowSums ( flow )[ 1 ] == colSums ( flow )[ nV ])# 最終的な最大フローネットワークグラフの重み付き隣接行列。mxFlow <- pmax ( flow , 0 ) print ( list ( "残差ネットワークグラフ" = rGraph )) print ( list ( "最大フロー" = mxFlow ))

参考文献

1 2 3コーメン, TH ; Leiserson, CE ; Rivest, ルイジアナ州;スタイン、C. (2001)。「§26 最大流量」。アルゴリズム入門(第 2 版)。 MITプレス。643 –698ページ。ISBN 978-0262032933。
1 2 3 4 5 6 7 Goldberg, AV; Tarjan, RE (1986). 「最大フロー問題への新しいアプローチ」。第18回ACM理論計算機科学シンポジウム（STOC '86）議事録。p . 136。doi : 10.1145 /12130.12144。ISBN 978-0897911931. S2CID 14492800 .
1 2 Ahuja, Ravindra K.; Kodialam, Murali; Mishra, Ajay K.; Orlin, James B. (1997). "最大フローアルゴリズムの計算的調査". European Journal of Operational Research . 97 (3): 509. CiteSeerX 10.1.1.297.2945 . doi : 10.1016/S0377-2217(96)00269-X .
1 2 3 Goldberg, Andrew V. (2008). "最大フロー問題に対する部分拡張・再ラベルアルゴリズム". Algorithms – ESA 2008. Lecture Notes in Computer Science. Vol. 5193. pp. 466–477 . CiteSeerX 10.1.1.150.5103 . doi : 10.1007/978-3-540-87744-8_39 . ISBN 978-3-540-87743-1。
↑ Goldberg, Andrew V (1997). "スケーリング最小コストフローアルゴリズムの効率的な実装". Journal of Algorithms . 22 : 1–29 . doi : 10.1006/jagm.1995.0805 .
↑ Ahuja, Ravindra K.; Orlin, James B. (1991). "最大フローおよびパラメトリック最大フロー問題に対する距離指向型拡大パスアルゴリズム". Naval Research Logistics . 38 (3): 413. CiteSeerX 10.1.1.297.5698 . doi : 10.1002/1520-6750(199106)38:3 < 413::AID-NAV3220380310 > 3.0.CO ; 2-J .
1 2 3 4 5 6 Goldberg, Andrew V.; Tarjan, Robert E. (1988). "最大フロー問題への新しいアプローチ" . Journal of the ACM . 35 (4): 921. doi : 10.1145/48014.61051 . S2CID 52152408 .
↑ Goldberg, Andrew V.; Tarjan, Robert E. (2014). "効率的な最大フローアルゴリズム". Communications of the ACM . 57 (8): 82. doi : 10.1145/2628036 . S2CID 17014879 .
1 2 Ahuja, RK; Magnanti, TL; Orlin, JB (1993). Network Flows: Theory, Algorithms, and Applications (1st ed.). Prentice Hall. ISBN 978-0136175490。
↑ Shiloach, Yossi; Vishkin, Uzi (1982). "An O(n2log n) parallel max-flow algorithm". Journal of Algorithms . 3 (2): 128– 146. doi : 10.1016/0196-6774(82)90013-X .
↑ Cheriyan, J.; Maheshwari, SN (1988). 「最大ネットワークフローのためのプリフロープッシュアルゴリズムの分析」. Foundations of Software Technology and Theoretical Computer Science . Lecture Notes in Computer Science. Vol. 338. p. 30. doi : 10.1007/3-540-50517-2_69 . ISBN 978-3-540-50517-4。
↑ Cherkassky, Boris V.; Goldberg, Andrew V. (1995). "最大フロー問題に対するプッシュリラベル法の実装について".整数計画法と組合せ最適化. コンピュータサイエンス講義ノート. 第920巻. 157ページ. CiteSeerX 10.1.1.150.3609 . doi : 10.1007/3-540-59408-6_49 . ISBN 978-3-540-59408-6。
↑デリッグス、U.マイヤー、W. (1989)。「Goldberg の max-flow アルゴリズムの実装? 計算による調査」。オペレーションズリサーチの時代。33 (6): 383.土井: 10.1007/BF01415937。S2CID 39730584。

[clrs26-1] 1 2 3コーメン, TH ; Leiserson, CE ; Rivest, ルイジアナ州;スタイン、C. (2001)。「§26 最大流量」。アルゴリズム入門(第 2 版)。 MITプレス。643 –698ページ。ISBN 978-0262032933。

[goldberg86-2] 1 2 3 4 5 6 7 Goldberg, AV; Tarjan, RE (1986). 「最大フロー問題への新しいアプローチ」。第18回ACM理論計算機科学シンポジウム（STOC '86）議事録。p . 136。doi : 10.1145 /12130.12144。ISBN 978-0897911931. S2CID 14492800 .

[ahuja97-3] 1 2 Ahuja, Ravindra K.; Kodialam, Murali; Mishra, Ajay K.; Orlin, James B. (1997). "最大フローアルゴリズムの計算的調査". European Journal of Operational Research . 97 (3): 509. CiteSeerX 10.1.1.297.2945 . doi : 10.1016/S0377-2217(96)00269-X .

[goldberg08-4] 1 2 3 Goldberg, Andrew V. (2008). "最大フロー問題に対する部分拡張・再ラベルアルゴリズム". Algorithms – ESA 2008. Lecture Notes in Computer Science. Vol. 5193. pp. 466–477 . CiteSeerX 10.1.1.150.5103 . doi : 10.1007/978-3-540-87744-8_39 . ISBN 978-3-540-87743-1。

[goldberg97-5] Goldberg, Andrew V (1997). "スケーリング最小コストフローアルゴリズムの効率的な実装". Journal of Algorithms . 22 : 1–29 . doi : 10.1006/jagm.1995.0805 .

[ahuja91-6] Ahuja, Ravindra K.; Orlin, James B. (1991). "最大フローおよびパラメトリック最大フロー問題に対する距離指向型拡大パスアルゴリズム". Naval Research Logistics . 38 (3): 413. CiteSeerX 10.1.1.297.5698 . doi : 10.1002/1520-6750(199106)38:3 < 413::AID-NAV3220380310 > 3.0.CO ; 2-J .

[goldberg88-7] 1 2 3 4 5 6 Goldberg, Andrew V.; Tarjan, Robert E. (1988). "最大フロー問題への新しいアプローチ" . Journal of the ACM . 35 (4): 921. doi : 10.1145/48014.61051 . S2CID 52152408 .

[goldberg2014-8] Goldberg, Andrew V.; Tarjan, Robert E. (2014). "効率的な最大フローアルゴリズム". Communications of the ACM . 57 (8): 82. doi : 10.1145/2628036 . S2CID 17014879 .

[amo93-9] 1 2 Ahuja, RK; Magnanti, TL; Orlin, JB (1993). Network Flows: Theory, Algorithms, and Applications (1st ed.). Prentice Hall. ISBN 978-0136175490。

[sv82-10] Shiloach, Yossi; Vishkin, Uzi (1982). "An O(n2log n) parallel max-flow algorithm". Journal of Algorithms . 3 (2): 128– 146. doi : 10.1016/0196-6774(82)90013-X .

[cheriyan88-11] Cheriyan, J.; Maheshwari, SN (1988). 「最大ネットワークフローのためのプリフロープッシュアルゴリズムの分析」. Foundations of Software Technology and Theoretical Computer Science . Lecture Notes in Computer Science. Vol. 338. p. 30. doi : 10.1007/3-540-50517-2_69 . ISBN 978-3-540-50517-4。

[cherkassky95-12] Cherkassky, Boris V.; Goldberg, Andrew V. (1995). "最大フロー問題に対するプッシュリラベル法の実装について".整数計画法と組合せ最適化. コンピュータサイエンス講義ノート. 第920巻. 157ページ. CiteSeerX 10.1.1.150.3609 . doi : 10.1007/3-540-59408-6_49 . ISBN 978-3-540-59408-6。

[derigs89-13] デリッグス、U.マイヤー、W. (1989)。「Goldberg の max-flow アルゴリズムの実装? 計算による調査」。オペレーションズリサーチの時代。33 (6): 383.土井: 10.1007/BF01415937。S2CID 39730584。

[

[

[

[

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9

Yossi

[ 11 ]

[ 12 ]

[ 13 ]

歴史

概念