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

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. static void Main(string[] args)
2. {
3.   Console.Write("Podaj ile jest wierzchołków w grafie\n n = ");
4.   int n = Convert.ToInt32(Console.ReadLine());
5.   Console.Write("Podaj węzeł początkowy\n s = ");
6.   int s = Convert.ToInt32(Console.ReadLine());
7.   Console.Write("Podaj węzeł końcowy\n t = ");
8.   int t = Convert.ToInt32(Console.ReadLine());
9.   int[,] macierz = new int[n, n];
10.   for (int i = 0; i < n; i++)
11.   {
12.     string[] str = Console.ReadLine().Split(' ');
13.     for (int j = 0; j < n; j++)
14.     {
15.       macierz[i, j] = Convert.ToInt32(str[j]);
16.     }
17.   }
18.   dane[] tab = BFS(macierz, s);
19.   int przeplyw = AlgorytmDinitza(macierz, s, t);
20.   Console.WriteLine("Maksymalny przepływ wynosi {0}", przeplyw);
21.   Console.ReadKey();
22. }

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