エドモンズ・カープアルゴリズム

コンピュータサイエンス において、エドモンズ・カープアルゴリズムは、フローネットワークにおける最大フローを時間内で計算するためのフォード・フルカーソン法の実装です。このアルゴリズムは、1970年にイェフィム・ディニッツによって初めて公開され、 ^{[1] [2]} 、 1972年にジャック・エドモンズとリチャード・カープによって独立して公開されました。^[3]ディニッツのアルゴリズムには、実行時間を^[2]に短縮する追加技術が含まれています${\displaystyle O(|V||E|^{2})}$ ${\displaystyle O(|V|^{2}|E|)}$

アルゴリズム

このアルゴリズムは、増加経路を見つける際の探索順序が定義されていることを除いて、フォード・フルカーソンアルゴリズムと同一です。発見される経路は、利用可能な容量を持つ最短経路でなければなりません。これは、各辺に重み1を適用する幅優先探索によって見つけることができます。実行時間は、各増加経路が時間内に発見できること、 E個の辺のうち少なくとも1つが飽和状態になるたびに（最大フローを持つ辺）、飽和した辺から増加経路に沿ったソースまでの距離は、前回飽和したときよりも長くなければならないこと、そして長さが最大であることを示すことによって求められます。このアルゴリズムのもう1つの特性は、最短増加経路の長さが単調に増加することです。^[4]これらの特性を用いた証明の概要は次のとおりです ${\displaystyle O(|V||E|^{2})}$ ${\displaystyle O(|E|)}$ ${\displaystyle |V|}$

証明はまず、残余フローネットワークにおけるソースノードsから任意の非シンクノードvまでの最短経路の距離が、各増加反復後に単調に増加することを証明する（補題1、以下で証明）。次に、各エッジがアルゴリズムの実行時間中、ほとんどの時間でクリティカルとなり得ることを示し、増加反復の上限を与える。各反復には 時間がかかるため（幅優先探索を用いて最短経路を見つけるのにかかる時間で制限される）、エドモンズ・カープ法の総実行時間は要求される値となる。^[4]${\displaystyle |E|}$ ${\displaystyle {\frac {|V|}{2}}}$ ${\displaystyle O\left({\frac {|V||E|}{2}}\right)=O(|V||E|)}$ ${\displaystyle O(|E|)}$ ${\displaystyle O(|V||E|^{2})}$

補題1を証明するには、sからvへの最短経路距離を減少させる増加反復があると仮定することで、背理法を用いることができます。fをそのような増加前のフローとし、を増加後のフローとします。残差フローネットワークにおけるノードからの最小距離をと表記します。 を示すことで矛盾を導き出すことができます。これは、ソースノードsと非シンクノードvの間の最短経路距離が実際には減少していないことを意味します。^[4]${\displaystyle f'}$ ${\displaystyle G_{f}}$ ${\displaystyle u,v}$ ${\displaystyle \delta _{f}(u,v)}$ ${\displaystyle \delta _{f}(s,v)\leq \delta _{f'}(s,v)}$

擬似コード

アルゴリズムEdmondsKarpの
    入力：
        グラフ   (graph[v] は、元のグラフの頂点 v から出ているエッジ
                と、プッシュバックフローに使用される、対応する構築された逆エッジのリストである必要があります。各エッジには、容量 'cap'、フロー、ソース 's'、シンク 't' がパラメーターとして含まれ、逆エッジ 'rev' へのポインタも含まれています。) 
        s        (ソース頂点) 
        t        (シンク頂点)出力:
                
                
                
    
        流量    （最大流量の値）
    
    flow := 0    (フローをゼロに初期化します) 
    repeat 
        (最短経路を見つけるために幅優先探索 (bfs) を実行します。
        各頂点に到達するために使用されたエッジを保存するために 'pred' を使用します。
        これにより、後で経路を復元できます) 
        q := queue ()
        q.push(s)
        pred := array (graph.length)
        かつ空で はない(q)かつpred[t] = null
            cur := q.pop()
            graph[cur]のEdge eに対して、 pred[et] = nullかつet ≠ sかつe.cap > e.flowの場合には、
                 
                    pred[et] := e
                    q.押す(et)

        if  not (pred[t] = null) then 
            (増加パスが見つかりました。
            どのくらいのフローを送れるか確認します)  
            df := ∞ 
            for (e := pred[t]; e ≠ null; e := pred[es]) do 
                df := min (df, e.cap - e.flow)
             (そしてその量だけエッジを更新します) 
            for (e := pred[t]; e ≠ null; e := pred[es]) do
                e.flow := e.flow + df
                e.rev.flow := e.rev.flow - df
            フロー := フロー + df

    pred[t] = null  となるまで（つまり、増加パスが見つからなくなるまで）
    フロー
を返す

例

以下に示す7つのノード、ソースA、シンクG、および容量を持つネットワークがあるとします

辺に書かれたペアのうち、は現在の流量、は容量です。 から までの残余容量は、総容量から既に使用された流量を差し引いたものです。 から までの正味流量が負の場合、残余容量に 寄与します。${\displaystyle f/c}$ ${\displaystyle f}$ ${\displaystyle c}$ ${\displaystyle u}$ ${\displaystyle v}$ ${\displaystyle c_{f}(u,v)=c(u,v)-f(u,v)}$ ${\displaystyle u}$ ${\displaystyle v}$

パス	容量	結果として得られるネットワーク
${\displaystyle A,D,E,G}$	${\displaystyle {\begin{aligned}&\min(c_{f}(A,D),c_{f}(D,E),c_{f}(E,G))\\=&\min(3-0,2-0,1-0)\\=&\min(3,2,1)=1\end{aligned}}}$
${\displaystyle A,D,F,G}$	${\displaystyle {\begin{aligned}&\min(c_{f}(A,D),c_{f}(D,F),c_{f}(F,G))\\=&\min(3-1,6-0,9-0)\\=&\min(2,6,9)=2\end{aligned}}}$
${\displaystyle A,B,C,D,F,G}$	${\displaystyle {\begin{aligned}&\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,D),c_{f}(D,F),c_{f}(F,G))\\=&\min(3-0,4-0,1-0,6-2,9-2)\\=&\min(3,4,1,4,7)=1\end{aligned}}}$
${\displaystyle A,B,C,E,D,F,G}$	${\displaystyle {\begin{aligned}&\min(c_{f}(A,B),c_{f}(B,C),c_{f}(C,E),c_{f}(E,D),c_{f}(D,F),c_{f}(F,G))\\=&\min(3-1,4-1,2-0,0-(-1),6-3,9-3)\\=&\min(2,3,2,1,3,6)=1\end{aligned}}}$

アルゴリズムによって発見された増加パス（赤で表示）の長さが決して減少しないことに注目してください。発見されたパスは可能な限り最短です。発見されたフローは、ソースとシンクを分けるグラフの最小カットを横切る容量に等しくなります。このグラフには、ノードを集合 と に分割する最小カットが1つだけあり、容量は ${\displaystyle \{A,B,C,E\}}$ ${\displaystyle \{D,F,G\}}$

${\displaystyle c(A,D)+c(C,D)+c(E,G)=3+1+1=5.\ }$

注釈

1. ディニッチ、EA (1970). 「電力推定を伴うネットワークにおける最大フロー問題の解法アルゴリズム」ソビエト数学 - ドクラディ. 11.ドクラディ: 1277–1280
2. イェフィム・ディニッツ (2006). 「ディニッツのアルゴリズム：オリジナル版とエヴェン版」(PDF) .オデッド・ゴールドライヒ、アーノルド・L・ローゼンバーグ、アラン・L・セルマン編. 『理論計算機科学：シモン・エヴェン追悼エッセイ集』 シュプリンガー. pp.  218– 240. ISBN 978-3-540-32880-3。
3. エドモンズ、ジャック、カープ、リチャード・M. (1972). 「ネットワークフロー問題におけるアルゴリズム効率の理論的改善」(PDF) . Journal of the ACM . 19 (2): 248– 264. doi :10.1145/321694.321699. S2CID  6375478
4. Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein (2009). 「26.2」.アルゴリズム入門（第3版）. MIT Press. pp.  727– 730. ISBN 978-0-262-03384-8。

参考文献

1. アルゴリズムと複雑性（63～69ページ参照）https://web.archive.org/web/20061005083406/http://www.cis.upenn.edu/~wilf/AlgComp3.html