الگوریتم ادموندز کارپ

الگوریتم ادموندز کارپ (به انگلیسی: Edmonds-Karp algorithm): در علوم کامپیوتر و نظریه گراف الگوریتمEdmonds_Karp پیاده‌سازی ای برای الگوریتم فورد–فالکرسون برای محاسبهٔ مسئله بیشینه جریان در شبکه شاره در زمان $O(|V||E|^{2})$

است. این الگوریتم از الگوریتم ارسال-برچسب که در زمان

O(|V|^{3})

انجام می‌شود سریع تر است. این الگوریتم اولین بار توسط دانشمند شوروی Yefim (Chaim) Dinic در سال ۱۹۷۰ منتشر شد؛ و به‌طور مستقل توسط جک ادموند و ریچارد کارپ در سال ۱۹۷۲ با کاهش زمان الگوریتم قبلی به

O(|V||E|^{2})

انتشار یافته‌است.

الگوریتم

در این اگوریتم می‌خواهیم بیشینه شاره را از مبدأ s تا مقصد t پیدا کنیم این الگوریتم شبیه به الگوریتم الگوریتم فورد–فالکرسون است و تفاوتش این است که در این الگوریتم محدودیت الگوریتم فورد–فالکرسون بهبود می‌یابد چرا که که محاسبهٔ مسیر افزایشی را با جستجوی سطح اول پیاده‌سازی می‌کنیم. حال آنکه در الگوریتم فورد–فالکرسون جستجوی عمق اول را اجرا می‌کردیم و به محدودیت زمانی بیشتری نیاز داشت. مسیر پیدا شده باید کوتاه‌ترین مسیر باشد که ظرفیت آماده‌ای دارد؛ که توسط جستجوی سطح اول پیدا می‌شود؛ که ما اجازه می‌دهیم یال‌ها اندازهٔ واحدی داشته باشند. بیشترین شاره معادل با برش کمینه است. ویژگی دیگر این الگوریتم این است که طول کوتاه‌ترین مسیر هر سری افزایش می‌یابد. اثبات را می‌توان ار منبع ذکر شده مشاهده کرد کاری که در این الگوریتم می‌کنیم این است که با جستجوی سطح اول مسیر افزایشی را می‌یابیم و هر سری اگر که مسیر افزایشی (مسیری که یال پر ندارداین مسئله هم در کد سطح اولی که در زیر آمده مشخص است) داشتیم کمترین ظرفیت را پیدا می‌کند و مینیمم ظرفیت را به جریان همهٔ یال هااضافه می‌کند و از آن کم می‌کند. به این صورت بیشینه شار بین مبدأ و مقصد را پیدا می‌کند که معادل با برش کمینه است. در کد زیر نحوهٔ انجام این الگوریتم نشان داده می‌شود. ورودی الگوریتم: ورودی این الگوریتم یک گراف است که یک راس مبدأ s دارد و یک راس مقصد t و روی همهٔ یال‌ها ظرفیت هر یال نوشته شده‌است. خروجی الگوریتم: بیشترین جریان از s به t تا زمانی که مسیر افزایشی با ویژگی‌های بالا وجود دارد.

پیچیدگی الگوریتم

زمان اجرای این الگوریتم $O(|V||E|^{2})$

است. به این علت که هر مسیر در زمان اجرای

O(|E|)

بدست می‌آید. در هر زمان حداقل یکی از E یال سیر می‌شوند؛ که فاصله از یال سیر شده تا مبدأ باید طولانی‌تر از آخرین باری باشد که سیر شده و این طول حداکثر برابر با V تعداد راس‌ها است.

پیاده‌سازی

algorithm EdmondsKarp
     input:
         C[1..n, 1..n] (Capacity matrix)
         E[1..n, 1.. ?](Neighbour lists)
         s            (Source)
         t             (Sink)
    output:
         f            (Value of maximum flow)
         F             (A matrix giving a legal flow with the maximum value)
     f:= 0 (Initial flow is zero)
     F:= array(1..n, 1..n) ''(Residual capacity from u to v is C[u,v] - F[u,v])
     forever
         m, P:= BreadthFirstSearch(C, E, s, t, F)
         if m = ۰
            break
         f:= f + m
        (Backtrack search, and write flow)
         v:= t
        while v ≠ s
             u:= P[v]
             F[u,v]:= F[u,v] + m
             F[v,u]:= F[v,u] - m
             v:= u
    return (f, F)

 algorithm BreadthFirstSearch
     input:
         C, E, s, t, F
     output:
         M[t]         (Capacity of path found)
         P            (Parent table)
     P:=array(1..n)
    for u in 1..n
         P[u]:= -۱
     P[s]:= -2(make sure source is not rediscovered)
     M:=array(1..n)(Capacity of found path to node)
     M[s]:= ∞
     Q:= queue()
     Q.push(s)
     while Q.size()> ۰
         u:= Q.pop()
        for v in E[u]
            (If there is available capacity, and v is not seen before in search)
             if C[u,v] - F[u,v]> 0 and P[v] = -۱
                 P[v]:= u
                 M[v]:= min(M[u], C[u,v] - F[u,v])
                if v ≠ t
                     Q.push(v)
                else
                     'return M[t], P
    return 0, P

مثال

در شکل زیر گرافی داده شده‌است که روی یال‌هایش ظرفیت هر یالی قرار دارد و جریان اولیهٔ گذر کرده از یال‌ها برابر با ۰ است می‌خواهیم جریان بیشینه که از A به G می‌رود را پیدا کنیم.

در شکل‌های زیر مراحل مختلف الگوریتم قرار گرفته و در هر شکل یک مسیر با ویژگی‌های ذکر شده با جستجوی عمق اول پیدا شده و در زیر هر شکل مراحل مختلف مربوط به آن قرار گرفته. در زیر هر شکل ظرفیت باقی‌مانده محاسبه شده که برابر با (cf(u,v) = c(u,v) − f(u,v است و طبق الگوریتم بالا بین ظرفیت‌های باقی ماندهٔ یال‌های الگوریتم مقدار حداقلی یافت می‌شود.

ظرفیت	مسیر
ظرفیت	شبکهٔ راس‌ها
min(c_f(A,D),c_f(D,E),c_f(E,G)) = min(3-0,2-0,1-0) = min(3,2,1) = ۱	A,D,E,G

min(c_f(A,D),c_f(D,F),c_f(F,G)) = min(3-1,6-0,9-0) = min(2,6,9) = ۲	A,D,F,G

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) = ۱	A,B,C,D,F,G

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) = ۱	A,B,C,E,D,F,G

در آخر می‌خواهیم بیشینه جریان را پیدا کینم. می‌دانیم که جریان بیشینه برابر با برش کمینه است. در این شکل یک برش کمینه وجود دارد که راس‌ها را به راس‌های A B C E وو D F G تقسیم می‌کند با ظرفیت زیر: c(A,D)+c(C,D)+c(E,G)=۳+۱+۱=۵

منابع

↑ ^ E. A. Dinic (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation". Soviet Math. Doklady (Doklady) 11: 1277–1280
↑ ^ Jack Edmonds and Richard M. Karp (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM 19 (2): 248–264. doi:10.1145/321694.321699.
↑ ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). "26.2". Introduction to Algorithms (second ed.). MIT Press and McGraw–Hill. pp. 660–663. ISBN 0-262-53196-8.

الگوریتم‌ادموندز کارپ (انگلیسی)

پیوند به بیرون

example.com

[1] E. A. Dinic (1970). "Algorithm for solution of a problem of maximum flow in a network with power estimation". Soviet Math. Doklady (Doklady) 11: 1277–1280

[2] Jack Edmonds and Richard M. Karp (1972). "Theoretical improvements in algorithmic efficiency for network flow problems". Journal of the ACM 19 (2): 248–264. doi:10.1145/321694.321699.

[3] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein (2001). "26.2". Introduction to Algorithms (second ed.). MIT Press and McGraw–Hill. pp. 660–663. ISBN 0-262-53196-8.