W mojej implementacji algorytmu Dijkstry mam 1 tablicę ze wszystkimi węzłami i jedną kolejkę priorytetową ze wszystkimi węzłami. Za każdym razem, gdy węzeł jest usuwany, aktualizuję wszystkie sąsiednie węzły o nową odległość i skąd pochodzi, więc mogę wycofać ścieżkę.Algorytm Dijkstry z kolejką priorytetową
Węzeł w kolejce priorytetów jest aktualizowany o nową odległość, a węzeł w tablicy jest aktualizowany, skąd przybył iz nową odległością. Kiedy węzeł jest rozkolejkowywana ostateczna odległość w tablicy jest aktualizowany:
PathInfo current = pq.remove();
path[current.pos].distance = current.distance;
Czy dopuszczalne jest, aby zaktualizować zarówno tablicę z informacją o poprzednim węzłem a kolejki priorytetowej z oddali?
Dzieje się tak, gdy odległość jest lepszy znaleziono:
PathInfo key(i, newDistance);
path[i].distance = newDistance;
path[i].previous = current.pos;
pq.decreaseKey(key);
Wydaje się nieco zbędny zaktualizować tablicę i kolejkę priorytetową z zasadniczo tej samej informacji.
Obecnie używam zwykłej tablicy jako struktury danych w PQ. Aktualizowanie priorytetu odbywa się w czasie liniowym, a puszczanie odbywa się również w czasie liniowym.
Jakiej struktury danych należy użyć w kolejce priorytetowej i jak zmienić priorytet węzłów?
Używam C++
Muszę zaktualizować odległości w tablicy. Jak inaczej mam się porównywać, czy węzeł z mojego PQ może dać lepszy dystans do sąsiednich węzłów? – Carlj901
Idealnie powinieneś być w stanie wyszukać to ze swojego PQ. Jeśli ta operacja jest niedostępna (i nie można jej dodać do implementacji PQ), będziesz musiał zachować nadmiarowe informacje. [Dodam sekcję na ten temat do mojej odpowiedzi] – comingstorm
Najbardziej preferowane byłoby, gdybym mógł utrzymać stertę w moim PQ i mieć funkcję mieszającą, która mapuje nazwę każdego węzła (pozycja w tablicy 2D) na jego odległość. Nie jestem pewien, jak to zrealizować. – Carlj901