Najlepsze pytania
Chronologia
Czat
Perspektywa
Algorytm Edmondsa-Karpa
Z Wikipedii, wolnej encyklopedii
Remove ads
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 jest zatem wolniejszy od innych znanych algorytmów przepływowych działających w czasie 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 (algorytm z tą poprawką nazywa się obecnie algorytmem Dynica).
Remove ads
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 zdefiniuj r[u,v] jako c[u,v] – f[u,v] ścieżka := true dopóki ścieżka wykonaj // znalezienie ś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 f[v,u] = f[v,u]-a
Remove ads
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 kroków algorytmu (czyli jest co najwyżej kroków, jako że długość ścieżki nie przekroczy ).
Remove ads
Przykład
Podsumowanie
Perspektywa
Dana jest następująca sieć przepływowa:
Wierzchołek A jest źródłem, G ujściem. Pary liczb na krawędziach oznaczają odpowiednio bieżący przepływ i maksymalną pojemność krawędzi. Pojemność residualna krawędzi z do to 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ć.
Remove ads
Zobacz też
Przypisy
Linki zewnętrzne
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads