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

数理最適化におけるアルゴリズム

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

プッシュ・リラベルアルゴリズムは、最も効率的な最大フローアルゴリズムの1つと考えられています。この汎用アルゴリズムは、強多項式O(V2E)の時間計算量を持ち $、$ これ $は漸近的に O$ (VE2)のエドモンズ・カープアルゴリズムよりも効率的です $。 [2]$ このアルゴリズム $の$ ^{特定のバリアントは} $、$ さらに低い時間計算量を実現します。最高のラベルノード選択ルールに基づくバリアントは、O(V2√E)の時間計算量を持ち $、$ $一般的に最大フロー$ アルゴリズムのベンチマークと見なされています。^[3]^[4]動的木を使用することで、サブキュービック $O (VElog (V2 / E)) の$ 時間計算量を実現できますが、^[2]実際には効率が低くなります。^[^要出典^]

プッシュ・リラベルアルゴリズムは、最小コストフローを計算するために拡張されました。^[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(V2E) で終了するアルゴリズムの一般的な形式 $に加えて、O(V3$ $) のシーケンシャル実装$ 、 $動的ツリー$ $を$ $使用$ $し$ た $O (VElog (V2 / E)) の$ 実装、および並列/分散実装が詳述されている。 [ $2$ ^]^[7]で説明されているように、^{[9] Goldberg–Tarjan は、Yossi Shiloach と}Uzi Vishkinの並列最大フロー・アルゴリズムに距離ラベルを組み込むことによって距離ラベルを導入した。^[10]

概念

定義と表記

させて：

$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

,

v

) \in

E

f

に対して

𝓁(

u

) \leq 𝓁(

v

) + 1 が成り立つ

ソース条件:

𝓁(s) = | V |

シンク保全：

𝓁(t) = 0

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

弧 $(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 |$ となるように初期化され、他のすべてのノードにはゼロのラベルが与えられます。初期化が完了すると、アルゴリズムは、適用可能な操作が実行できなくなるまで、アクティブなノードに対してプッシュ操作または再ラベル操作を繰り返し実行します。

押す

$プッシュ操作は、 G$ $f$ 内のアクティブノード $u$ の許容アウトアーク $(u, v)$ に適用されます。この操作は、 $uから$ $v$ へ $min{$ $x$ $f$ $($ $u$ $),$ $c$ $f$ $($ $u$ $,$ $v$ $)}$ 単位のフローを移動させます。

push(u, v):
     x _f [u] > 0 かつ 𝓁[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] += Δ

$f (u, v)を$ $c (u, v)$ に到達させるプッシュ操作は、残余弧の利用可能な容量をすべて使い果たすため、飽和プッシュと呼ばれます。そうでない場合、ノードにおける超過分はすべて残余弧を越えてプッシュされます。これは、非飽和プッシュまたは非飽和プッシュと呼ばれます。

再ラベル

$再ラベル操作は、 G$ $f$ において許容されるアウトアークを持たない、ソースでもシンクでもないアクティブノード $u$ に適用されます。この操作は、 $𝓁($ $u$ $)$ を、許容されるアウトアークが形成される最小値に変更します。この操作により、 $𝓁($ $u$ $)$ は常に増加し、急勾配のアーク $（ c$ $f$ $ ($ $u$ $,$ $v$ $) > 0 かつ$ $𝓁($ $u$ $) >𝓁($ $v$ $) + 1$ となるようなアーク $($ $u$ $,$ $v$ $) ）$ は作成されないことに注意してください。

relabel(u):
     c _f [u] [v] > 0となるすべてのvに対してx _f [ u] > 0かつ𝓁[u] <= 𝓁[v]をアサートする_{𝓁[u] = 1 + min(𝓁[v]、c f} [u][v] > 0

    となるすべてのvについて)

プッシュと再ラベルの効果

プッシュまたは再ラベル操作の後も、 $𝓁は$ $f$ に関して有効なラベリング関数のままです。

許容弧 $(u 、 v)に対するプッシュ操作では、$ $E$ $f$ に弧 $(v 、 u)$ が追加されることがあります。ここで、 $𝓁($ $v$ $) = 𝓁($ $u$ $) - 1 \leq 𝓁($ $u$ $) + 1です。また、$ $E$ $f$ から弧 $($ $u$ $、$ $v$ $)$ が削除されることもあります。その場合、制約 $𝓁($ $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$ $}$ に対して自明に有効です。初期化後、アルゴリズムは適用可能なプッシュまたは再ラベル操作を、そのような操作が適用されなくなるまで繰り返し実行し、その時点でプレフローは最大フローに変換されます。

ジェネリックプッシュ再ラベル(G, c, s, t):
    s のすべてのアウトアークを飽和させるプリフロー f を作成する
    𝓁[s] = |V|
    とし、適用可能なプッシュまたは再ラベル操作がある限り、すべての v ∈ V \ {s} に対して 𝓁[v] = 0 と
    する。
        操作を実行する

正確さ

アルゴリズムは、実行中、 $𝓁$ が有効なラベル付けであるという条件を維持します。これは、ラベル関数 $𝓁$ に対するプッシュおよび再ラベル付け操作の効果を調べることによって証明できます。再ラベル付け操作は、ラベル値を関連する最小値に1を加えた値だけ増加させ、常に $𝓁(u) \leq 𝓁(v) + 1制約を満たします。𝓁$ $($ $u$ $) = 𝓁($ $v$ $) + 1$ の場合、プッシュ操作は $uから$ $v$ にフローを送ることができます。これにより、 $G$ $f$ に $($ $v$ $,$ $u$ $)$ が追加され、 $G$ $f$ から $($ $u$ $,$ $v$ $)が削除される可能性があります。𝓁$ $($ $v$ $) = 𝓁($ $u$ $) - 1であるため、$ $G$ $f$ への $($ $v$ $,$ $u$ $)$ の追加は有効なラベル付けに影響を与えません。 $G$ $f$ から $($ $u$ $,$ $v$ $)$ を削除すると、対応する制約が削除されます。これは、有効なラベル付け特性 $𝓁($ $u$ $) \leq 𝓁($ $v$ $) + 1 が$ $G$ $f$ の残差弧にのみ適用されるためです。^[7]

プリフロー $fと$ $f$ に対する有効なラベリング $𝓁 が$ 存在する場合、残差グラフ $G$ $f$ $にはsから$ $t$ への増加パスは存在しません。これは、増加パスが存在すると仮定した場合にラベリング関数で生じる不等式に基づく矛盾によって証明できます。アルゴリズムが終了した場合、 $V$ $\ {$ $s$ $,$ $t$ $}$ 内のすべてのノードはアクティブではありません。これは、すべての $v$ $\in$ $V$ $\ {$ $s$ $,$ $t$ $}$ に過剰フローがないことを意味し、過剰がない場合はプリフロー $fはフロー保存制約に従い、通常のフローと見なすことができます。このフローは、$ $sから$ $t$ への増加パスが存在しないため、最大フロー最小カット定理によれば最大フローです。^[7]

したがって、アルゴリズムは終了時に最大フローを返します。

時間計算量

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

このアルゴリズムでは、再ラベル操作は最大 $(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$ をアクティブ化し、 $Φ を$ 最大で $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 (V2)$ 回のラベル付け、 $O (VE)$ 回の飽和プッシュ、そして $O (V2E)$ $回$ $の$ $非飽和プッシュを実行する。データ構造は、適切な操作を$ $O (1)$ 回で選択して実行するように設計することができる。したがって、このアルゴリズムの時間計算量は $O$ $(V2E) で$ ある。 $[$ ^1]^[7]

例

以下は、上記で定義した汎用プッシュ再ラベルアルゴリズムを次の単純なネットワークフローグラフダイアグラムで実行するサンプルです。

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

アルゴリズム操作	残差グラフ
プリフローの値を 0 に設定し、ラベル付けを初期化して残差グラフを初期化します。
初期飽和プッシュは、ソース $s$ からのすべてのプリフローアークにわたって実行されます。
ノード $a は、$ その過剰フローをシンク $t$ に向かって押し出すために再ラベル付けされます。次に、 $a$ の超過分は $b$ にプッシュされ、その後2 回の飽和プッシュで $dにプッシュされます。それでも$ $a$ にはまだ余剰が残ります。

もう一度、 $a の$ ラベルを変更して、その超過分を最後に残った正の残差に沿って押し進めます（つまり、超過分を $s$ に戻します）。その後、ノード $a$ はアクティブノードのセットから削除されます。

$b の$ ラベルを変更し、その余剰部分を $t$ と $c$ にプッシュします。
$c の$ ラベルを変更し、その超過分を $d$ にプッシュします。
$d の$ ラベルを変更し、その超過分を $t$ にプッシュします。
これにより、ノード $b$ が唯一残ったアクティブノードになりますが、過剰なフローをシンクに向かってプッシュすることはできません。 $b$ に再ラベルを付け、その超過分をノード $aを介してソース$ $s$ に向かってプッシュします。

最後の余剰分を $a$ でソース $s$ に戻します。アクティブなノードは残っていません。アルゴリズムは終了し、グラフの最大フローを返します（上記参照）。

この例 (ただし初期フローは 0) はここで対話的に実行できます。

実践的な実装

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

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

「カレントアーク」データ構造は、フローネットワーク内のノードの入側と出側の隣接ノードを静的な循環順序で参照するためのメカニズムです。ノードに対して隣接ノードの単方向リンクリストを作成する場合、データ構造はリストへのポインタのように単純化できます。このポインタはリストを1つずつ処理し、終端に達したら先頭に戻ります。

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

放電(u):
     x _f [u] > 0の場合、電流アーク[u]が近傍[u]の端を越えているならば、
        
            再ラベル(u)
            電流アークを巻き戻す[u]
        そうでなければ
            (u, v) = current-arc[u]
            とし、 (u, v) が許容可能な場合は
                プッシュ(u, v)
            current-arc[u]をuの次の隣接点を指すように
する

次にプッシュする許容可能なエッジを見つけるには、償却計算量が存在します。現在のアークのポインタは、現在の隣接ノードへのエッジが飽和または非許容である場合にのみ、次の隣接ノードに移動します。これらの2つの特性は、アクティブノードが再ラベル付けされるまで変化しません。したがって、ポインタが移動してしまうと、許容可能な非飽和エッジは存在しなくなり、アクティブノードを再ラベル付けする必要があります。つまり、ポインタを回移動させたことの代償として、再ラベル付け操作が必要になります。^[7] $O(1)$ $u$ $u$ $O(V)$ $O(V)$

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

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

FIFO選択ルール

FIFOプッシュ・リラベルアルゴリズム^[2]は、アクティブノードをキューに整理する。最初のアクティブノードは任意の順序で挿入できる。このアルゴリズムは常にキューの先頭のノードを削除して排出する。非アクティブノードがアクティブになると、そのノードはキューの最後尾に追加される。

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

前面への再ラベル選択ルール

再ラベル・トゥ・フロントプッシュ・リラベルアルゴリズム^[1]は、すべてのノードをリンクリストに整理し、リストが許容ネットワークに関して位相的にソートされているという不変条件を維持する。このアルゴリズムはリストを先頭から末尾に向かってスキャンし、現在のノードがアクティブであれば、そのノードに対してディスチャージ操作を実行する。ノードが再ラベル付けされている場合、そのノードはリストの先頭に移動し、先頭からスキャンを再開する。

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

最高ラベル選択ルール

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

このアルゴリズムには時間計算量がある。代わりに最低ラベル選択規則を用いると、時間計算量は $O$ $($ $V$ $2$ $E$ $)$ となる。^[3] $O(V^{2}{\sqrt {E}})$

実装技術

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

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

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

サンプル実装

C実装

#include <stdlib.h> #include <stdio.h> 
 

#define NODES 6 
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y)) 
#define INFINITE 10000000

void 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 ;              
        

  過剰= ( int * ) calloc ( NODES , sizeof ( int ));高さ= ( int * ) calloc ( NODES , sizeof ( int ));見られたもの= ( int * ) calloc ( NODES , sizeof ( int ));     
       
       

  リスト= ( int * ) calloc ( ( NODES -2 )、sizeof ( int ));     

  for ( i = 0 , p = 0 ; i < NODES ; i ++ ){ if (( i != source ) && ( i != sink )) { list [ p ] = i ; p ++ ; } }          
            
        
      
    
  

  高さ[ソース] = NODES ;過剰[ソース] = INFINITE ; for ( i = 0 ; i < NODES ; i ++ ) push ( C , F ,過剰,ソース, 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 ];  
        
       
       
         
        
       
        
      
        
    
  
     
         
      

  free (リスト);

  自由（見られる）；
自由（高さ）；自由（超過）；  
  

  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 (容量);  

  printf ( "最大フロー: \n %d \n " , pushRelabel (容量,フロー, 0 , 5 ));    

  printf ( "フロー: \n " ); 
printMatrix ( flow );  

  0を返す; }

Python実装

def relabel_to_front ( C , source : int , sink : int ) -> int : """Push–relabel最大フローアルゴリズム。""" 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   # 最後の再ラベル付け以降に確認された隣接
    ノード # ノードが「キュー」
    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 ] += send  
             
          
          
          
          

    def 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 + 1 
        
        
          
           
                 
                   
                    

    def discharge ( u ): while excess [ u ] > 0 : if seen [ u ] < n : # 次の隣接ノードをチェックv = seen [ u ] if C [ u ][ v ] - F [ u ][ v ] > 0かつheight [ u ] > height [ v ]: push ( u , v ) else : seen [ u ] += 1 else : # すべての隣接ノードをチェックしました。再ラベル付けが必要ですrelabel ( u ) seen [ u ] = 0 
           
                 
                  
                         
                     
                
                      
              
                
                  

    height [ 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  +=  1

     sumを返す（F [ソース]）

R {ベース}実装

# (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 )) }    
      
           
           
               
            
           
      


再ラベル<- function ( u ) {高さ[ u ] <<-高さ[ 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 ) }   
       
         
      
     
        
  
      


# プリフロー: 保存制約が緩和されたフロー: 流入 ≥ 流出。
# 過剰フローを許容エッジを越えてシンクに向かって移動します。
# グローバル データ eCap、rGraph、excess、height。1 から始まる頂点 ID でインデックス付けされます。pushRelabel 
< - function ( source 、sink ) { rGraph <<- eCap # 残差ネットワーク グラフ。excess <<- #流入- 流出 (≥ 0)。height << - rep ( 0L 、nV ) # ラベル (𝓁) 値。    
                         
                             
                   

  高さ[ソース] <<- nV過剰[ソース] <<- Inf relabCtr <<- pushCtr <<- 0L # 再ラベル、プッシュをカウントします。  
    
               

  
# ソースから余分なものをプッシュします。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 ( "Capacity matrix" = 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 ( "Residual network graph" = rGraph )) print ( list ( "Maximum flow" = mxFlow ))

参照

講義ノートTim Roughgarden、「アルゴリズムの 2 番目のコース (CS261、2016 年冬)」、コロンビア大学、ニューヨーク。

参考文献

^ abc Cormen, TH ; Leiserson, CE ; Rivest, RL ; Stein, C. (2001). 「§26 最大フロー」.アルゴリズム入門（第2版）. MIT Press. pp. 643–698. ISBN 978-0262032933。
^ abcdefg Goldberg, AV; Tarjan, RE (1986). 「最大フロー問題への新しいアプローチ」.第18回ACMコンピューティング理論シンポジウム（STOC '86）の議事録. p. 136. doi :10.1145/12130.12144. ISBN 978-0897911931. S2CID 14492800。
^ ab 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.
^ abc 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.
^ abcdef 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.
^ ab Ahuja, RK; Magnanti, TL; Orlin, JB (1993).ネットワークフロー：理論、アルゴリズム、およびアプリケーション（第1版）. Prentice Hall. ISBN 978-0136175490。
^ Shiloach, Yossi; Vishkin, Uzi (1982). 「O(n2log n)並列最大フローアルゴリズム」. Journal of Algorithms . 3 (2): 128– 146. doi :10.1016/0196-6774(82)90013-X.
^ Cheriyan, J.; Maheshwari, SN (1988). 「ネットワークフローを最大化するプリフロープッシュアルゴリズムの分析」.ソフトウェア技術と理論計算機科学の基礎. 計算機科学講義ノート. 第338巻. p. 30. doi :10.1007/3-540-50517-2_69. ISBN 978-3-540-50517-4。
^ チェルカスキー, ボリス V.; ゴールドバーグ, アンドリュー V. (1995). 「最大フロー問題に対するプッシュ・リラベル法の実装について」.整数計画法と組合せ最適化. コンピュータサイエンス講義ノート. 第920巻. p. 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] Cormen, TH ; Leiserson, CE ; Rivest, RL ; Stein, C. (2001). 「§26 最大フロー」.アルゴリズム入門（第2版）. MIT Press. pp. 643–698. ISBN 978-0262032933。

[goldberg86-2] Goldberg, AV; Tarjan, RE (1986). 「最大フロー問題への新しいアプローチ」.第18回ACMコンピューティング理論シンポジウム（STOC '86）の議事録. p. 136. doi :10.1145/12130.12144. ISBN 978-0897911931. S2CID 14492800。

[ahuja97-3] 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] 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] 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] Ahuja, RK; Magnanti, TL; Orlin, JB (1993).ネットワークフロー：理論、アルゴリズム、およびアプリケーション（第1版）. Prentice Hall. ISBN 978-0136175490。

[sv82-10] Shiloach, Yossi; Vishkin, Uzi (1982). 「O(n2log n)並列最大フローアルゴリズム」. Journal of Algorithms . 3 (2): 128– 146. doi :10.1016/0196-6774(82)90013-X.

[cheriyan88-11] Cheriyan, J.; Maheshwari, SN (1988). 「ネットワークフローを最大化するプリフロープッシュアルゴリズムの分析」.ソフトウェア技術と理論計算機科学の基礎. 計算機科学講義ノート. 第338巻. p. 30. doi :10.1007/3-540-50517-2_69. ISBN 978-3-540-50517-4。

[cherkassky95-12] チェルカスキー, ボリス V.; ゴールドバーグ, アンドリュー V. (1995). 「最大フロー問題に対するプッシュ・リラベル法の実装について」.整数計画法と組合せ最適化. コンピュータサイエンス講義ノート. 第920巻. p. 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。