خوارزمية إدموندز-كارب

في علوم الكمبيوتر ، خوارزمية إدموندز-كارب هي تنفيذ لطريقة فورد-فولكرسون لحساب التدفق الأقصى في شبكة تدفق في الوقت المناسب. تم نشر الخوارزمية لأول مرة بواسطة يفيم دينيتز في عام 1970، ^{[1] [2]} ونشرها بشكل مستقل جاك إدموندز وريتشارد كارب في عام 1972. ^{[3] تتضمن} خوارزمية دينيتز تقنيات إضافية تقلل من وقت التشغيل إلى . ^[2]${\displaystyle O(|V||E|^{2})}$ ${\displaystyle O(|V|^{2}|E|)}$

الخوارزمية مماثلة لخوارزمية فورد-فولكرسون ، باستثناء أن ترتيب البحث عند العثور على مسار الزيادة محدد. يجب أن يكون المسار الموجود هو أقصر مسار متاح السعة. يمكن العثور على ذلك من خلال بحث العرض أولاً ، حيث نطبق وزنًا قدره 1 على كل حافة. ​​يتم العثور على وقت تشغيل من خلال إظهار أنه يمكن العثور على كل مسار زيادة في الوقت المناسب، وأنه في كل مرة يصبح فيها أحد الحواف على الأقل مشبعًا (حافة بها أقصى تدفق ممكن)، وأن المسافة من الحافة المشبعة إلى المصدر على طول مسار الزيادة يجب أن تكون أطول من آخر مرة كانت مشبعة فيها، وأن الطول هو . خاصية أخرى لهذه الخوارزمية هي أن طول أقصر مسار زيادة يزداد بشكل رتيب. يوجد دليل يمكن الوصول إليه في مقدمة الخوارزميات . ^[4]${\displaystyle O(|V||E|^{2})}$${\displaystyle O(|E|)}$${\displaystyle E}$${\displaystyle |V|}$

خوارزمية EdmondsKarp هي 
    المدخل :
        يجب أن يكون الرسم البياني    (graph[v] عبارة عن قائمة بالحواف الخارجة من الرأس v في 
                الرسم البياني الأصلي والحواف العكسية المبنية المقابلة لها 
                والتي تُستخدم للتدفق العكسي. 
                يجب أن يكون لكل حافة سعة "cap"، وتدفق، ومصدر "s" ومصب "t" 
                كمعلمات، بالإضافة إلى مؤشر للحافة العكسية "rev".) 
        s        (رأس المصدر) 
        t        (رأس المصب) 
    output :
        التدفق     (قيمة التدفق الأقصى)
    
    التدفق := 0    (تهيئة التدفق إلى الصفر) 
    التكرار 
        (قم بتشغيل بحث أولًا بالعرض (bfs) للعثور على أقصر مسار st. 
        نستخدم "pred" لتخزين الحافة المأخوذة للوصول إلى كل رأس، 
        حتى نتمكن من استعادة المسار بعد ذلك) 
        q := queue ()
        q.push(s)
        pred := array (graph.length)
         while  not empty(q) and pred[t] = null
            cur := q.pop()
            بالنسبة للحافة e في الرسم البياني [cur]، افعل ذلك 
                إذا كان pred[et] = null  و et ≠ s و e.cap > e.flow ، إذن
                    pred[et] := e
                    س.ادفع(و)

        إذا  لم يكن (pred[t] = null) إذن 
            (لقد وجدنا مسارًا متزايدًا. 
            انظر إلى مقدار التدفق الذي يمكننا إرساله)  
            df := ∞ 
            بالنسبة إلى (e := pred[t]؛ e ≠ null؛ e := pred[es]) افعل 
                df := min (df، e.cap - e.flow)
             (وتحديث الحواف بهذا المقدار) 
            بالنسبة إلى (e := pred[t]؛ e ≠ null؛ e := pred[es]) افعل
                التدفق الإلكتروني := التدفق الإلكتروني + df
                e.rev.flow := e.rev.flow - df
            التدفق := التدفق + df

    حتى pred[t] = null   (أي حتى لم يتم العثور على مسار زيادة)
     تدفق
 العودة

بالنظر إلى شبكة مكونة من سبع عقد، المصدر 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 أ، د، هـ، ز}$	${\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 أ،د،و،ز}$	${\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}}}$

لاحظ كيف أن طول مسار الزيادة الذي وجدته الخوارزمية (باللون الأحمر) لا يتناقص أبدًا. المسارات التي وجدتها هي الأقصر قدر الإمكان. التدفق الذي وجدته يساوي السعة عبر الحد الأدنى للقطع في الرسم البياني الذي يفصل المصدر عن المصب. يوجد حد أدنى واحد فقط للقطع في هذا الرسم البياني، يقسم العقد إلى مجموعات و ، مع السعة ${\displaystyle \{A,B,C,E\}}$${\displaystyle \{D,F,G\}}$

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

1. الخوارزميات والتعقيد (انظر الصفحات 63-69). https://web.archive.org/web/20061005083406/http://www.cis.upenn.edu/~wilf/AlgComp3.html