Algorytm Dijkstry

Powrót do listy wątków

Czy można tak skonstruować graf ( odpowiednio duży ), aby ten algorytm ( działający na kolejce priorytetowej ) przestał działać z powodu zapchania się tej kolejki ( bo w tym podejściu trzymamy zbędne informacje ) ? Paweł Maśluch, 2015-04-26 22:13:27
zamiast kolejki priorytetowej (priority_queue) możesz użyć np. seta z odpowiednio dobranym komparatorem. Wtedy możesz zrobić erase w czasie logarytmicznym. W przypadku algorytmu Dijkstry wygląda to w taki sposób, że jak potrzebujesz zaktualizować oszacowanie wagi ścieżki do jakiegoś wierzchołka to: usuwasz go na chwilę z seta, poprawiasz w tablicy co tam chcesz i wrzucasz ponownie (bez tego myku się rozwali). Stała schowana w notacji O jest trochę gorsza, natomiast sama złożoność się nie pogarsza (no i tak jak chciałeś - będziesz mógł trzymać na secie tylko to co chcesz).
Alternatywą jest napisanie własnego kopca, który jest nieco rozszerzony o reverse index do każdego elementu (dla każdego wierzchołka musisz wiedzieć gdzie on jest w kopcu). Karol Pokorski, 2015-04-27 19:00:33