Algorytm Dinica dla Maksymalnego Przepływu

Dlaczego Algorytm Plain Edmonds-Karp Nadeszcza Zgasnąć

Algorytm Edmonds-Karp jest standardowym rozwiązaniem dla problemów nieokreśloności Forda-Fulkersona: zamiast wybierać losową ścieżkę wzmocnienia, zawsze używa algorytmu przeszukiwania wszerz (BFS) aby znaleźć najkrótszą ścieżkę wzmocnienie pod względem liczby krawędzi. To gwarantuje zakończenie i granicę O(V razy E do kwadratu), ale algorytm nadal traktuje każdą pojedynczą ścieżkę wzmocnienia jako osobny incydent. Po przesunięciu przepływu wzdłuż jednej ścieżki, całe drzewo BFS jest odrzucane i następna iteracja przeszukuje graf resztkowy ponownie z pustego arkusza, nawet jeśli większość struktury grafu nie uległa zmianie. W przypadku grafów z wieloma równoległymi ścieżkami prawie najkrótszych, oznacza to ponowne wykonywanie bardzo podobnych przeszukiwań wszerz wiele razy, ponosząc pełny koszt O(E) dla każdej znalezionej ścieżki. Straty pracy nie wynikają z błędnego znajdowania ścieżek, ale z zapominania wszystkiego, czego się nauczyło, po znalezieniu tylko jednej. Kluczowym spostrzeżeniem Dinica było to, że pojedyncze przeszukanie BFS ujawnia już najkrótszą odległość od źródła do każdego węzła, a ta informacja pozostaje ważna do przesunięcia przepływu wzdłuż wielu ścieżek, o ile te ścieżki przestrzegają tej samej warstwy. Zamiast jednej ścieżki wzmocnienia na każde BFS, algorytm Dinica wyodrębnia cały maksymalny pakiet ścieżek wzmocnieniowych, zwany przepływem blokującym, z pojedynczej grafy poziomej przed uruchomieniem BFS ponownie. Przepływ blokujący to przypisanie przepływu, w którym każda ścieżka źródło-cel w grafie poziomym ma co najmniej jedną nasyconą krawędź, co oznacza, że ​​nie można przesłać dodatkowego przepływu przez graf poziomowy bez przekroczenia pojemności którejś z krawędzi. Znalezienie tego przepływu blokującego nadal wymaga przeszukania, ale może być wykonane za pomocą jednego przeszukiwania w głąb pogłębionego wzmocnionego o prowadniki, zamiast jednego przeszukania na ścieżkę. W rezultacie kosztowne ponowne budowanie BFS zachodzi tylko O(V) razy w całym algorytmie, zamiast raz na każdą ścieżkę wzmocnienia, a to restrukturyzowanie jest tym, co oddziela złożoność algorytmu Dinica od złożoności algorytmu Edmonds-Karp.

Budowanie Grafu Poziomowego z Wykorzystaniem Przeszukiwań Wąkolistych

Każda faza algorytmu Dinica rozpoczyna się od autentycznego przeszukiwania wąkolistego, uruchomionego z węzła źródłowego na aktualnej grafie resztkowej, czyli grafie utworzonym dla każdego krawędzi, która nadal posiada pojemność pozostałą po uwzględnieniu przepływu już przesuniętego wzdłuż niej i jej odwrotnej. Przeszukiwanie wąkolistowe przypisuje każdemu osiągalnemu węźłowi numer poziomu równy minimalnej liczbie krawędzi resztkowych potrzebnych do jego dotarcia z źródła, dokładnie taka sama ilość, jaką obliczyłoby standardowe przeszukiwanie najkrótszej ścieżki wąkolistowe. Zachowuje się jedynie krawędzie, które przemieszczają się z poziomu L na poziom L+1; każda krawędź resztkowa łącząca węzły na tym samym poziomie lub wskazująca wstecz do niższego poziomu jest odrzucana, nawet jeśli ma ona wolną pojemność. To przycinanie jest kluczowe i to właśnie ono utrzymuje efektywność kolejnego przeszukiwania głębokimi poszukiwaniami, ponieważ gwarantuje, że każdy znaleziony w grafie poziomowy ścieżka automatycznie jest najkrótszą ścieżką w grafie resztkowej oraz zapobiega marnowaniu czasu przez DFS na wędrowanie do martwych gałęzi lub cykli. Jeśli przeszukiwanie wąkolistowe zakończy się bez dotarcia do węzła docelowego, jest to sygnał zakończenia algorytmu: nigdzie w grafie resztkowym nie istnieje ścieżka augmentacyjna, graf poziomowy jest pusty i bezużyteczny, a aktualny przepływ już stanowi maksymalny przepływ, zgodnie z twierdzeniem o maksimum przepływu i minimalnym cięciu. Budowanie grafu poziomego kosztuje O(E) czasu i O(V) czasu na samą operację przemieszczenia się, ponieważ przeszukiwanie wąkolistowe odwiedza każdy węzeł raz i bada każdą krawędź najwyżej raz. Warto podkreślić, że graf poziomowy jest grafem skierowanym bez cykli dzięki konstrukcji, ponieważ krawędzie ściśle zwiększają poziom, a ta własność bezcykliczna jest dokładnie tym, dlaczego faza DFS następna może bezpiecznie używać książki pamięciowej z pojedynczym wskaźnikiem bez ponownego odwiedzania w pełni zbadanej martwej gałęzi więcej niż raz. Każdego uruchomienia tego przeszukiwania wąkolistego gwarantuje, że najkrótsza odległość od źródła do celu zmierzona w grafie resztkowym zwiększy się w stosunku do poprzedniej fazy, co stanowi podstawę dowodu złożoności algorytmu.

Znajdowanie Przepływu Blokującego przy Użyciu Przeszukiwań Wąsowtolistowych

Z ustalonym grafem poziomowym na tym etapie, algorytm Dinica przechodzi do przeszukiwania wszerz (DFS) którego zadaniem jest znalezienie przepływu blokującego, czyli maksymalnego zbioru ścieżek augmentacyjnych przez graf poziomowy, takich że nie można przez niego położyć żadnej dodatkowej jednostki przepływu. Przeszukiwanie WS rozpoczyna się od źródła i wędruje bezustannie w przód wzdłuż krawędzi grafu poziomowego, zawsze przechodząc na wyższy poziom, aż do momentu osiągnięcia pompy lub napotkania martwego punktu bez możliwości kontynuowania poszukiwań. W przypadku osiągnięcia pompy przepływ równy minimalnej przepustowości ścieżki jest przekazywany wzdłuż odkrytej ścieżki. Jeśli jednak napotykany punkt dead-end nie posiada żadnych dostępnych krawędzi, przeszukiwanie WS cofamy się do tyłu. Kluczową optymalizacją wydajności jest utrzymywanie dla każdego węzła aktualnego wskaźnika lub indeksu iteratora w jego liście sąsiedztwa. Po całkowitym nasyceniu danej krawędzi, lub po ustaleniu, że węzeł nie może dotrzeć do pompy, ten wskaźnik jest przesuwany dalej, nie będąc ponownie rozważany podczas tej fazy. Oznacza to, że każda krawędź grafu poziomowego jest badana i odrzucana maksymalnie raz na fazę, a nie raz na ścieżkę augmentacyjną, więc cały poszukiwanie przepływu blokującego w całym grafie kosztuje w najgorszym przypadku tylko O(V razy E), ponieważ każda z do O(V) ścieżek augmentacyjnych może wymagać O(V) krawędzi do przejścia, a przesuwanie wskaźników amortyzuje koszty skanowania krawędzi. Ten pojedynczy przebieg DFS, przekazywający przepływ po wielu ścieżkach bez ponownego uruchamiania, jest mechanicznym rdzeniem przewagi Dinica pod względem szybkości. Gdy przeszukiwanie WS przestaje dotykać pompy z źródła przy użyciu nasyconych krawędzi grafu poziomowego, przepływ blokujący dla tej fazy jest zakończony. Niektóre węzły mogą stać się trwale martwe w połowie tego procesu, a oznaczanie ich tak, aby przeszukiwanie WS nigdy nie wracało do nich, jest kolejną ważną optymalizacją księgowości, która zapobiega bezowemu ponownemu badaniu.

Wymiana faz i gwarancja zakończenia

Gdy dany etap osiąga pełne nasycenie przepływu blokującego, algorytm całkowicie odrzuca bieżący graf poziomu i wraca do przeszukiwania wszerz, budując nowy, od podstawowy graf poziomu na podstawie resztkowych pojemności pozostających po zablokowanym przepływie. Ta alternacja – przeszukiwanie wszerz w celu zbudowania struktury, a następnie wykorzystanie jej w pełni – przeszukiwanie wszerz ponownie w celu ponownego zbudowania – jest powtarzana aż do momentu, gdy przeszukiwanie wszerz danego etapu nie dociera do węzła docelowego, w którym to momencie algorytm zatrzymuje się i zgromadzony przepływ jest wykazany jako maksymalny. Argument poprawności opiera się na klasycznym lemmie: odległość najkrótszej ścieżki z źródła do węzła docelowego w grafie resztkowym jest niezbyt zmniejszana w fazach, a faktycznie wzrasta po każdej fazie przepływu blokującego. Intuicyjnie, gdy dany etap nasyca wszystkie najkrótsze ścieżki danego długości, wszelkie pozostałe drogi augmentacyjne w grafie resztkowym muszą podążać za dłuższym szlakiem, ponieważ wszystkie krótkie mają co najmniej jeden wąski punkt. Ponieważ odległość najkrótszej ścieżki jest ograniczona powyżej przez liczbę węzłów i wzrasta o co najmniej jeden po każdej fazie, może być maksymalnie O(V) faz w sumie przed tym, że odległość musiałaby przekroczyć V, co jest niemożliwe, wymuszając zakończenie. Jest to znacznie silniejsza gwarancja zakończenia niż oferowana pośrednio przez algorytm Edmonds-Karp, który ogranicza liczbę ścieżek augmentacyjnych bezpośrednio do O(V razy E) zamiast ograniczać liczbę faz, w których każdy etap algorytmu Dinica może obsługiwać potencjalnie wiele ścieżek jednocześnie. Pomnożenie limitu faz O(V) przez koszt każdego etapu – BFS plus praca blokująca – daje ogólny złożoność czasowa O(V do kwadratu razy E), a na grafach gęstych lub bardzo połączonych może to być dramatyczny ulepszenie w praktyce, zwłaszcza gdy wiele rzeczywistych sieci przepływowych ma znacznie mniej niż liczbę faz w najgorszym przypadku, co jest typowe.

Gdzie Algorytm Dinica Zajmuje Pozycję Wśród Metod Maksymalnego Przepływu

Algorytm Dinica znajduje się w rodzinie technik maksymalnego przepływu, które wywodzą się z metody Forda-Fulkersona, ogólnego ramy polegającej na wielokrotnym znajdowaniu ścieżek wzmocnienia w grafie resztkowym, aż nie pozostaną żadne. Prosta metoda Forda-Fulkersona, wykorzystująca arbitralną selekcję ścieżek, np. przeszukiwanie w głąb (DFS) bez jakiejkolwiek dyscypliny warstwowej, może bardzo źle działać na grafach z irracjonalnymi lub źle dobranymi pojemnościami, a nawet zawieść i nie zakończyć działania w przypadku patologicznych przypadków o całkowicie zmiennych pojemnościach, jeśli jest źle zaimplementowana. Algorytm Edmonds-Karp poprawia to, wymagając najkrótszych ścieżek wzmocnienia, ale za tę gwarancję płaci powtarzanymi pełnymi poszukiwaniami w całym grafie. Algorytm Dinica zachowuje dyscyplinę szukania najkrótszej ścieżki, która sprawia, że algorytm Edmonds-Karp jest poprawny, a jednocześnie amortyzuje koszt poszukiwań na wielu ścieżkach na każdej fazie, dlatego jego złożoność ściśle poprawia się w stosunku do algorytmu Edmonds-Karp dla ogólnych grafów. Warto zauważyć, że na grafach o pojemności jednostkowej, takich jak te występujące w problemach dopasowywania bipartytnego, algorytm Dinica osiąga nawet lepszy wynik O(E razy pierwiastek z V), co jest częścią tego, dlaczego leży u podstaw wydajnych algorytmów dopasowywania bipartytnego, takich jak Hopcroft-Karp. Późniejsze udoskonalenia posuwały teorię przepływu jeszcze dalej, w tym implementacje opartych na drzewach link-cut, które osiągają O(V razy E razy log V) i, znacznie niedawno, algorytmy o zbliżonym czasie liniowym dla maksymalnego przepływu na ogólnych grafach, odkryte w latach 20. XX wieku. Mimo to, algorytm Dinica pozostaje podstawą w konkursowym programowaniu i powszechnym punktem odniesienia w systemach produkcyjnych, ponieważ jego dwufazowa struktura – warstwowe BFS (Breadth-First Search) i blokowanie przepływu DFS (Depth-First Search) – jest koncepcyjnie czysta, stosunkowo prosta do prawidłowej implementacji i wystarczająco szybka w praktyce dla ogromnej większości sieci przepływowych spotykanych poza ekstremalnymi teoretycznymi przypadkami najgorszego scenariusza. Jej dokładne badanie buduje również silną intuicję dotyczącą tego, jak struktury grafów warstwowe i amortyzowane prowadzenie wskaźników mogą przekształcić naiwne, wydające się kwadratowe wielokrotne przeszukiwanie w udowodniony, bardziej zwarty wynik.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Dinic's Algorithm for Maximum Flow i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.