Strona główna » Algorytmy » Artykuły » Algorytm Dinitza
 

Algorytm Dinitza

Wstęp

Algorytm opisany przez Yefim Dinitz pozwala określić maksymalny przepływ w sieci. W algorytmie wykorzystywany jest algorytm przeszukiwania wszerz BFS w celu wyznaczenia potrzebnych ścieżek pomiędzy wierzchołkami. W tym artykule zostanie opisany algorytm oraz wyjaśnione jak można go zaimplementować.

Algorytm

Algorytm składa się z kilku kroków:

Algorytm na wejście przyjmuje sieć G (graf) oraz punkty: początkowy s oraz końcowy t. Wynikiem będzie maksymalny przepływ sieci f pomiędzy wierzchołkami s i t.

  1. Każdej krawędzi przypisz fk = 0
  2. Znajdź ścieżkę od s do t, jeśli nie istnieje to zwróć f
  3. Oblicz przepływ ścieżki, dodaj go do f
  4. Zwiększ aktualnie wykorzystany przepływ dla każdej krawędzi ze ścieżki

Przykład

Przykładowo dany jest poniższy graf:

Graf G

Jest to graf skierowany w którym za s przyjmujemy wierzchołek A, a za końcowy t wierzchołek E. Przy każdej krawędzi jest napisany maksymalny przepływ tej krawędzi. Na ich podstawie zostanie wyszukany maksymalny przepływ w całym grafie. Pierwszy etap polega na przypisaniu każdej ścieżce fk = 0 i znalezienia pierwszej ścieżki.

Znaleziona Ścieżka A-B-C-E

Na rysunku pojawiło się oznaczenie f/X. Oznacza to, że zostało wykorzystane f z X. Na pomarańczowo została zaznaczona pierwsza znaleziona ścieżka (to zależy od sposobu implementacji algorytmu BSF). Kolejny krok polega na dodaniu do aktualnego przepływu f wartości ścieżki czyli 4 i aktualizacji przepływu na poszczególnych krawędziach grafu.

Zaznaczenie przepływu

Jak można zauważyć ścieżka B-C została całkowicie "zużyta", więc nie będzie można jej wziąć do ścieżki w następnych etapach. Proces powtarzamy, aż nie zostanie znaleziona ścieżka.

Ścieżka A-B-D-E, f = 2
Ścieżka A-D-E, f = 3
Brak ścieżki

Na ostatnim obrazku można zauważyć, że nie istnieje już ścieżka pomiędzy wierzchołkami A i E. Oznacza to, że algorytm kończy działanie. W wyniku otrzymujemy maksymalny przepływ sieci, który jest sumą wszystkich przepływów znalezionych ścieżek czyli 4 + 2 + 3 = 9. W tym grafie maksymalny przepływ f = 9. Jak widać istnieje możliwość zwiększenia przepływu jeśli zwiększy się przepływ na szarych krawędziach.

Implementacja

Poniższa funkcja AlgorytmDitritza() wykorzystuje algorytmu BSF. Przyjmuje ona macierz reprezentującą graf oraz indeks węzła początkowego i końcowego (przyjmujemy, że wierzchołki są indeksowane od 0).

C++C#
Python
  1. def AlgorytmDinitza(macierz, start, koniec):
  2.   f = 0
  3.   while True:
  4.     tab = BFS(macierz, start)
  5.     if tab[koniec].odleglosc == sys.maxsize:
  6.       return f
  7.     f_sciezka = sys.maxsize
  8.     teraz = koniec
  9.     while teraz != start:
  10.       rodzic = tab[teraz].poprzednik
  11.       f_sciezka = min(macierz[rodzic][teraz], f_sciezka)
  12.       teraz = rodzic
  13.     teraz = koniec
  14.     while teraz != start:
  15.       rodzic = tab[teraz].poprzednik
  16.       macierz[rodzic][teraz] -= f_sciezka
  17.       teraz = rodzic
  18.     f += f_sciezka

W nieskończonej pętli wyszukiwana jest ścieżka. Jeśli okaże się, że ścieżka nie istnieje tzn. ma nieskończoną odległość wierzchołek końcowy to ścieżka nie istnieje i zwracana jest wtedy aktualna wartość maksymalnego przepływu. Jeśli ścieżka istnieje to najpierw przechodzimy po kolejnych krawędziach i szukamy lokalnego przepływu. Po jego znalezieniu aktualizujemy przepływ całego grafu i dodatkowo zmniejszamy o tyle wartość krawędzi w zapisie macierzowym.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu kodu:

C++C#
Python
  1. n = int(input("Podaj ile węzłów ma graf\n n = "))
  2. s = int(input("Podaj węzeł startowy\n s = "))
  3. t = int(input("Podaj węzeł końcowy\n s = "))
  4. print("Podaj elementy macierzy:")
  5. macierz = []
  6. for i in range(0, n):
  7.   tab = [int(x) for x in input().split()]
  8.   macierz.append(tab)
  9. przeplyw = AlgorytmDinitza(macierz, s, t)
  10. print("aksymalny przepływ wynosi:", przeplyw)

Przykładowe dane testowe to:

  1. 5
  2. 0
  3. 4
  4. 0 8 0 3 0
  5. 0 0 4 2 0
  6. 0 0 0 0 5
  7. 0 0 0 0 7
  8. 0 0 0 0 0