Algorytm Edmondsa-Karpa
Z Wikipedii
Algorytm Edmondsa-Karpa jest jedną z realizacji metody Forda-Fulkersona rozwiązywania problemu maksymalnego przepływu w sieci przepływowej. Jego złożoność czasowa wynosi O(VE2), jest zatem wolniejszy od innych znanych algorytmów przepływowych działających w czasie O(V3), takich jak algorytm relabel-to-front, czy algorytm trzech Hindusów. W praktyce jednak złożoność pesymistyczna rzadko jest osiągana, co w połączeniu z prostotą czyni algorytm Edmondsa-Karpa bardzo użytecznym, szczególnie dla grafów rzadkich.
Algorytm ten został odkryty przez rosyjskiego naukowca, E. A. Dinica w roku 1970[1], i niezależnie przez Jacka Edmondsa i Richarda Karpa w roku 1972.[2]. Artykuł Dinica zawiera dodatkowe techniki, które obniżają czas działania do O(V2E) (algorytm z tą poprawką nazywa się obecnie algorytmem Dinica).
Spis treści |
[edytuj] Algorytm
Idea algorytmu jest identyczna z ideą metody Forda-Fulkersona, z dodatkowym warunkiem: ścieżka powiększająca, którą szukamy w każdym kroku algorytmu, musi być najkrótsza, czyli zawierać minimalną możliwą liczbę (nie wagę!) krawędzi. Taką ścieżkę znajduje się uruchamiając algorytm przeszukiwania grafu wszerz w sieci residualnej.
algorytm Edmonds-Karp wejście c[u,v] //pojemności krawędzi s,t //źródło i ujście wyjście f[u,v] //maksymalny przepływ // stworzenie sieci residualnej dla każdej krawędzi(u,v) r[u,v] := c[u,v] - f[u,v] ścieżka := true dopóki ścieżka wykonaj // znalezienie najkrótszej ścieżki z s do t w sieci residualnej p := BFS(r[],s,t) jeżeli ścieżka nie istnieje ścieżka := false w przeciwnym wypadku // powiększenie przepływu na ścieżce p a := min {r[u,v] : (u,v) należące do p} dla każdej krawędzi (u,v) należącej do p f[u,v] = f[u,v]+a r[u,v] = r[u,v]-a
[edytuj] Poprawność i złożoność
Poprawność algorytmu wynika wprost z twierdzenia Forda-Fulkersona: po zakończeniu działania w grafie nie może być ścieżki powiększającej, przepływ jest więc maksymalny. Przystępny dowód oszacowania złożoności czasowej można znaleźć w [3], opiera się on na fakcie, że długość ścieżki powiększającej nie może maleć, a utrzymywać się na tym samym poziomie może przez co najwyżej O(E) kroków algorytmu (czyli jest co najwyżej O(VE) kroków, jako że długość ścieżki nie przekroczy V).
[edytuj] Przykład
Dana jest następująca sieć przepływowa:
Wierzchołek A jest źródłem, G ujściem. Pary liczb f / c na krawędziach oznaczają odpowiednio bieżący przepływ i maksymalną pojemność krawędzi. Pojemność residualna krawędzi z u do v to r[u,v] = c[u,v] − f[u,v], pojemność maksymalna zmniejszona o aktualny przepływ. Należy zwrócić uwagę na to, że f[u,v] może być ujemne, co powiększa pojemność krawędzi.
W powstałej sieci nie ma już ścieżek powiększających, zatem znaleziony przepływ o wielkości 5 jest maksymalny. Przykład dobrze ilustruje podstawową własność algorytmu Edmondsa-Karpa: długości ścieżek powiększających w kolejnych krokach nie mogą maleć.
[edytuj] Zobacz też
[edytuj] Bibliografia
- ↑ E. A. Dinic, Algorithm for solution of a problem of maximum flow in a network with power estimation, Советский мат, том 11, Доклады 1970
- ↑ Jack Edmonds, Richard Karp, Theoretical improvements in algorithmic efficiency for network flow problems, Journal of the ACM, volume 19/1972, 248-264 (http://www.akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/08/Edmonds72.pdf)
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford Wprowadzenie do algorytmów, wyd. 7, WNT 2007, ISBN 83-204-3149-2.