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. int AlgorytmDinitza(int** macierz, int n, int start, int koniec) {
2.   int f = 0;
3.   while (true) {
4.     dane* tab = BFS(macierz, n, start);
5.     if (tab[koniec].odleglosc == INT32_MAX)
6.       return f;
7.     int f_sciezka = INT32_MAX;
8.     int teraz = koniec;
9.     while (teraz != start) {
10.       int rodzic = tab[teraz].poprzednik;
11.       f_sciezka = min(macierz[rodzic][teraz], f_sciezka);
12.       teraz = rodzic;
13.     }
14.     teraz = koniec;
15.     while (teraz != start) {
16.       int rodzic = tab[teraz].poprzednik;
17.       macierz[rodzic][teraz] -= f_sciezka;
18.       teraz = rodzic;
19.     }
20.     f += f_sciezka;
21.   }
22. }

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. int main() {
2.   int n, s, t;
3.   cout << "Podaj ile jest wierzcholkow w grafie\n n = ";
4.   cin >> n;
5.   cout << "Podaj wezel poczatkowy\n s = ";
6.   cin >> s;
7.   cout << "Podaj wezel koncowy\n t = ";
8.   cin >> t;
9.   int** macierz = new int*[n];
10.   for (int i = 0; i < n; i++) {
11.     macierz[i] = new int[n];
12.     for (int j = 0; j < n; j++) {
13.       cin >> macierz[i][j];
14.     }
15.   }
16.   int przeplyw = AlgorytmDinitza(macierz, n, s, t);
17.   cout << "Maksymalny przeplyw wynosi: " << przeplyw;
18.   system("pause");
19.   return 0;
20. }

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