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.

Szybkie fakty Rodzaj, Struktura danych ...

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:

Thumb

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.

Więcej informacji , ...

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

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads