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!