Dlaczego algorytm Dijkstry używa klawisza zmniejszania?

Nauczyłem się, że algorytm Dijkstry był następujący

while pqueue is not empty:
    distance, node = pqueue.delete_min()
    if node has been visited:
        continue
    else:
        mark node as visited
    if node == target:
        break
    for each neighbor of node:
         pqueue.insert(distance + distance_to_neighbor, neighbor)

Ale czytałem trochę na temat algorytmu i wiele wersji, które widzę, używa klawisza zmniejszania zamiast wstawiania.

Dlaczego tak jest i jakie są różnice między tymi dwoma podejściami?

Powodem używania klawisza zmniejszania zamiast ponownego wstawiania węzłów jest utrzymanie małej liczby węzłów w kolejce priorytetowej, dzięki czemu całkowita liczba usuwanych z kolejki priorytetowych jest niewielka, a koszt salda każdej kolejki priorytetowej jest niski.

W implementacji algorytmu Dijkstry, który ponownie wstawia węzły do ​​kolejki priorytetowej z ich nowymi priorytetami, jeden węzeł jest dodawany do kolejki priorytetów dla każdej z m krawędzi na grafie. Oznacza to, że w kolejce priorytetowej istnieją operacje m enqueue i m dequeue, co daje całkowity czas wykonania O (m T _e + m T _d ), gdzie T _e to czas wymagany do umieszczenia w kolejce priorytetowej, a T _d to czas potrzebny do usunięcia z kolejki priorytetowej.

W implementacji algorytmu Dijkstry, który obsługuje klawisz zmniejszania, kolejka priorytetowa, w której znajdują się węzły, zaczyna się od n węzłów i na każdym kroku algorytmu usuwa jeden węzeł. Oznacza to, że całkowita liczba usunięć z kolejki sterty wynosi n. Każdy węzeł będzie miał wywoływany klawisz zmniejszania potencjalnie raz dla każdej krawędzi prowadzącej do niego, więc całkowita liczba wykonanych klawiszy zmniejszania wynosi co najwyżej m. Daje to czas działania (n T _e + n T _d + m T _k ), gdzie T _k jest czasem wymaganym do wywołania klawisza zmniejszania.

Jaki to ma wpływ na środowisko wykonawcze? To zależy od używanej kolejki priorytetowej. Oto krótka tabela, która przedstawia różne kolejki priorytetowe i ogólne czasy wykonywania różnych implementacji algorytmów Dijkstry:

Queue          |  T_e   |  T_d   |  T_k   | w/o Dec-Key |   w/Dec-Key
---------------+--------+--------+--------+-------------+---------------
Binary Heap    |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Binomial Heap  |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Fibonacci Heap |  O(1)  |O(log N)|  O(1)  | O(M log N)  | O(M + N log N)

Jak widać, w przypadku większości typów kolejek priorytetowych tak naprawdę nie ma różnicy w asymptotycznym czasie wykonywania, a wersja z klawiszem zmniejszania prawdopodobnie nie będzie działać dużo lepiej. Jeśli jednak użyjesz implementacji kolejki priorytetowej stosu Fibonacciego , to rzeczywiście algorytm Dijkstry będzie asymptotycznie bardziej wydajny przy użyciu klawisza zmniejszania.

Krótko mówiąc, użycie klawisza zmniejszania oraz dobrej kolejki priorytetowej może obniżyć asymptotyczny czas działania Dijkstry poza to, co jest możliwe, jeśli nadal będziesz wykonywać kolejki i dekolejki.

Oprócz tego niektóre bardziej zaawansowane algorytmy, takie jak algorytm najkrótszych ścieżek Gabowa, używają algorytmu Dijkstry jako procedury podrzędnej i polegają w dużej mierze na implementacji klawisza zmniejszania. Korzystają z faktu, że znając zakres prawidłowych odległości z wyprzedzeniem, możesz zbudować super wydajną kolejkę priorytetów na podstawie tego faktu.

Mam nadzieję że to pomoże!

W 2007 roku ukazała się praca, w której badano różnice w czasie wykonania między wersją z klawiszem zmniejszającym a wersją z wkładką. Zobacz http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf

Ich podstawowym wnioskiem nie było użycie klawisza zmniejszania dla większości wykresów. Zwłaszcza w przypadku rzadkich wykresów klawisz bez zmniejszania jest znacznie szybszy niż wersja z klawiszem zmniejszania. Zobacz artykuł, aby uzyskać więcej informacji.

Istnieją dwa sposoby implementacji Dijkstry: jeden używa sterty obsługującej klawisz zmniejszania, a drugi sterty, która tego nie obsługuje.

Oba są ogólnie ważne, ale to drugie jest zwykle preferowane. W dalszej części użyję „m” do oznaczenia liczby krawędzi, a „n” do oznaczenia liczby wierzchołków naszego wykresu:

Jeśli chcesz uzyskać najlepszą możliwą złożoność w najgorszym przypadku, wybierz stertę Fibonacciego, która obsługuje klawisz zmniejszania: otrzymasz ładne O (m + nlogn).

Jeśli zależy Ci na przeciętnym przypadku, możesz również użyć stosu binarnego: otrzymasz O (m + nlog (m / n) logn). Dowód jest tutaj , strony 99/100. Jeśli wykres jest gęsty (m >> n), zarówno ten, jak i poprzedni mają tendencję do O (m).

Jeśli chcesz wiedzieć, co się stanie, jeśli uruchomisz je na prawdziwych wykresach, możesz zapoznać się z tym artykułem, jak zasugerował Mark Meketon w swojej odpowiedzi.

Wyniki eksperymentów pokażą, że w większości przypadków najlepsze wyniki da „prostsza” sterta.

W rzeczywistości, wśród implementacji, które używają klawisza zmniejszania, Dijkstra działa lepiej, gdy używa prostej sterty binarnej lub sterty parowania, niż gdy używa sterty Fibonacciego. Dzieje się tak, ponieważ sterty Fibonacciego obejmują większe stałe współczynniki, a rzeczywista liczba operacji klawiszem zmniejszania jest zwykle znacznie mniejsza niż przewiduje to najgorszy przypadek.

Z podobnych powodów sterta, która nie musi obsługiwać operacji klawiszem zmniejszania, ma jeszcze mniej stałych współczynników i faktycznie działa najlepiej. Zwłaszcza jeśli wykres jest rzadki.