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 f_k = 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 f_k = 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).

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:

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)
10. przeplyw = AlgorytmDinitza(macierz, s, t)
11. 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

• Kod źródłowy Implementacja