Modyfikacja algorytmu Dijkstry dla wag krawędzi pobranych z zakresu

10

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|)$ ?

— użytkownik1675999
źródło

Powinieneś bardziej szczegółowo: jaka jest twoja struktura danych? I nie możesz dostać mniej

O (V + E)

$O(V+E)$ . Przejrzyj wykłady.

— jonaprieto

To, że możliwości różnych obciążeń krawędzi są niewielkie, nie oznacza, że liczba odległości jest niewielka.

— Joe

3

Najpierw koloruj wierzchołki wykresu kolorem niebieskim, a następnie podziel każdą krawędź rozmiaru

na krawędzie

(dodając

bezbarwnych wierzchołków), a następnie uruchom BFS na tym nowym wykresie, aby znaleźć najkrótsze ścieżki od węzła początkowego do niebieskich węzłów, to jest

jeśli masz stałą

.

t

$t$

t

$t$

t - 1

$t-1$

O (| V | + | E |)

$O(|V|+|E|)$

k

$k$

@SaeedAmiri, dlaczego nie napisać tego jako odpowiedzi?

— Joe

@Joe, ponieważ nie modyfikuje dijkstra (przynajmniej bezpośrednio nie jest związany z dijkstra).

16

Jeśli wagi krawędzi są liczbami całkowitymi w , możesz zaimplementować Dijkstrę do działania w czasie , 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 jest wartością ostatniego klucza usuniętego z kolejki priorytetowej. (Każdy klucz ma co najmniej , ponieważ sekwencja kluczy usuniętych przez algorytm Dijkstry nie zmniejsza się, a każdy klucz ma co najwyżej , ponieważ każdy klucz ma wartość dla jakaś przewaga $\{D,D+1,\ldots,D+K\}$ $D$ $D$ $D+K$ $d[u] + wt(u,w)$ gdzie to odległość od źródła do jakiegoś wierzchołka który został już usunięty, więc ) $(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 , przy czym każda komórka zawiera segment. Przechowuj każdy wierzchołek z kluczem w wiadrze w komórce 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 . $A[h(D)]$ $D$ $A[h(D)]$
wstaw za pomocą klawisza : dodaj wierzchołek do segmentu . $k$ $A[h(k)]$
Klawisz zmniejszania do : Przenieś wierzchołek z do . $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|+|E|)$ $O(|V|)$ $D$ $D$ $i$ $D$ $i$ $K(|V|-1)$ $|V|-1$ $O(K|V|+|E|)$

— Neal Young
źródło

Podoba mi się kolejka kolista, jest to o wiele lepsze niż mój pomysł posiadania tablicy rozmiarów K * v, w której w danym momencie używany jest tylko kawałek wielkości av.

— rrenaud

Zaimplementowałem go za pomocą podwójnie połączonej listy, czy to nadal oznacza, że jest O (1) do znalezienia klucza min?

— user1675999,

@ user1675999, nie jestem pewien. jeśli twoja lista jest posortowana według klucza, jak efektywnie wstawiasz i zmniejszasz klawisz? jeśli twoja lista nie jest posortowana według klucza, jak zrobić wydajne usuwanie-min?

— Neal Young,

5

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. $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\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|)$

— rrenaud
źródło

-2

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.

— TIANYANG ZHANG
źródło

Wydaje się, że nie ma to związku z pytaniem? Pytanie nie zakłada, że wykres jest acykliczny, a twoje rozwiązanie nie korzysta z faktu, że wagi są rysowane ze stałego zakresu.

— xskxzr