Modyfikacja algorytmu Dijkstry dla wag krawędzi pobranych z zakresu

Załóżmy, że mam ukierunkowany wykres z wagami krawędzi narysowanymi z zakresu $[1,\dots, K]$ gdzie $K$ jest stałe. Jeśli próbuję znaleźć najkrótszą ścieżkę za pomocą algorytmu Dijkstry , jak mogę zmodyfikować strukturę algorytmu / danych i poprawić złożoność czasu do $O(|V|+|E|)$ ?

Jeśli wagi krawędzi są liczbami całkowitymi w , możesz zaimplementować Dijkstrę do działania w czasie O ( K | V | + | E | ) , zgodnie z sugestią @ rrenaud. Oto bardziej jednoznaczne wyjaśnienie.$\{0,1,\ldots,K\}$$O(K|V|+|E|)$

W dowolnym momencie (skończone) klucze w kolejce priorytetowej znajdują się w pewnym zakresie , gdzie D jest wartością ostatniego klucza usuniętego z kolejki priorytetowej. (Każdy klucz ma co najmniej D , ponieważ sekwencja kluczy usuniętych przez algorytm Dijkstry nie zmniejsza się, a każdy klucz ma co najwyżej D + K , ponieważ każdy klucz ma wartość d [ u ] + w t ( u , w ) dla jakaś przewaga ( u $\{D,D+1,\ldots,D+K\}$$D$$D$$D+K$$d[u] + wt(u,w)$ gdzie d [ u ] to odległość od źródła do jakiegoś wierzchołka u, który został już usunięty, więc d [ u ] ≤ D. )$(u,w)$$d[u]$$u$$d[u]\le D$

Z tego powodu można zaimplementować kolejkę priorytetową za pomocą okrągłej tablicy o rozmiarze K + 1 , przy czym każda komórka zawiera segment. Przechowuj każdy wierzchołek z kluczem k w wiadrze w komórce A [ h ( k ) ], gdzie . Śledzić . Wykonaj operacje w następujący sposób:$A[0..K]$$K+1$$k$$A[h(k)]$$h(k)=k \bmod (K+1)$$D$

• usunięta, min : Gdy jest pusta, przyrost . Następnie usuń i zwróć wierzchołek z .D A [ h ( D ) $A[h(D)]$$D$$A[h(D)]$

• wstaw za pomocą klawisza : dodaj wierzchołek do segmentu .A [ h ( k ) $k$$A[h(k)]$

• Klawisz zmniejszania do : Przenieś wierzchołek z do .k ′ A [ h ( k ) ] A [ h ( k ′ ) $k$$k'$$A[h(k)]$$A[h(k')]$

Klawisz wstawiania i zmniejszania są operacjami o stałym czasie, więc całkowity czas spędzony na tych operacjach będzie wynosił . Całkowity czas spędzony w usunięta, min będzie plus wartość końcowa . Ostateczna wartość jest maksymalny (Finite) odległość od źródła do każdego wierzchołka (ponieważ usuwania-min, że wykonuje iteracji zwiększa o ). Maksymalna odległość wynosi co najwyżej ponieważ każda ścieżka ma co najwyżej krawędzie . Zatem całkowity czas spędzony przez algorytm wynosi .O ( | V | ) D D i D i K ( | V | - 1 ) | V | - 1 O ( K | V | + | E |$O(|V|+|E|)$$O(|V|)$$D$$D$$i$$D$$i$$K(|V|-1)$$|V|-1$$O(K|V|+|E|)$

Zakładam tutaj, że jest liczbą całkowitą, a wagi krawędzi są integralne. W przeciwnym razie tak naprawdę nic ci nie kupisz, zawsze możesz przeskalować wagi tak, że minimalna krawędź ma koszt a maksymalna ma koszt , więc problem jest identyczny ze standardowym problemem najkrótszej ścieżki.1 $K$$1$$K$

Algorytm / szkic próbny: zaimplementuj kolejkę priorytetową w ten szalony sposób jako tablicęlisty wpisywane według kosztów i w inny sposób używają standardowego algorytmu Dijkstry. Trzymaj licznik, który śledzi koszt minimalnego przedmiotu na stosie. Rozwiąż wywołanie usuwania kolejki po usunięciu elementów przez skanowanie liniowe . Tak, ten rodzaj dźwięków jest szalony, ale stałe pozwala oszukiwać i oszukiwać algorytmiczną intuicję przed skanowaniem liniowym. Musisz tylko skanować od ostatniego znacznika min, ponieważ algorytm Disjkstry jest miły dla twojej implementacji kolejki. Do czasu żądania kolejkowania elementy wstawiane do kolejki są zawsze większe lub równe poprzedniemu minimum. Najdłuższa możliwa najkrótsza ścieżka ma długośćK K × | V | K × | V | = O ( | V |$K\times |V|$$K$$K\times |V|$, więc twój zamortyzowany koszt skanowania wynosi jeśli K jest stałe.$K\times |V| = O(|V|)$

możesz użyć sortowania topologicznego, aby znaleźć rozwiązanie, pozwól źródłu mieć stopień 0, a następnie przejdź od każdej krawędzi od źródła, jeśli inny wierzchołek ma 0 stopni, umieść go w kolejce i kontynuuj to. w tym przypadku (bez cyklu na wykresie) może osiągnąć V + E, ponieważ przechodziłby przez każdy wierzchołek i krawędzie raz i tylko raz.