Algorytm Dijkstry ze stosem kopcowym
Zachłanne znajdowanie najkrótszych ścieżek po krawędziach nieujemnych
Algorytm Dijkstry ze stosem kopcowym to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 1 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Problem najkrótszej ścieżki
Należy znaleźć najtańszą trasę z jednego wierzchołka do każdego innego. Dijkstra rozwiązuje ten problem, gdy każda waga krawędzi jest równa zero lub dodatnia.
Pomysł zachłanny
Algorytm Dijkstry jest zachłanny: zawsze rozwija nieodwiedzony wierzchołek o najmniejszej znanej odległości, uznając tę odległość za ostateczną.
Dlaczego kopiec minimalny
Aby szybko wybrać najbliższy wierzchołek, potrzebny jest kopiec minimalny. Zwraca on najmniejszą odległość w czasie log n zamiast wykonywać powolne wyszukiwanie liniowe.
import heapqRozpoczęcie odległości
Każdą odległość należy ustawić na nieskończoność, a następnie ustawić zero dla źródła. Nieosiągalne wierzchołki po prostu pozostają na zawsze w nieskończoności.
dist = [float('inf')] * n
dist[src] = 0Zainicjowanie kopca
Źródło należy umieścić w kopcu jako tuple postaci (odległość, wierzchołek). Umieszczenie odległości na pierwszym miejscu pozwala kopcowi automatycznie uporządkować elementy według kosztu.
pq = [(0, src)]Pobieranie najbliższego wierzchołka
W każdej iteracji należy wykonać pop najmniejszego elementu (d, u). Wartość d jest najkrótszą odległością do u, więc po pobraniu jego przetwarzanie jest zakończone.
d, u = heapq.heappop(pq)Pomijanie nieaktualnych elementów
W kopcu może znajdować się wierzchołek ze starą, większą odległością. Należy go pominąć, gdy d jest większe od zapisanej odległości.
if d > dist[u]:
continueRelaksacja sąsiadów
Relaksacja oznacza próbę poprawienia wyniku dla sąsiada: jeśli przejście przez u jest tańsze, należy zaktualizować jego odległość i umieścić go w kopcu.
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))Sztuczka z leniwym usuwaniem
Kopce w Pythonie nie pozwalają aktualizować klucza, dlatego umieszcza się w nich duplikaty i ignoruje nieaktualne elementy. Taki leniwy sposób pozwala zachować krótki i szybki kod.
Czas działania
W przypadku kopca binarnego algorytm Dijkstry działa w czasie O((V + E) log V). Taka złożoność bez problemu obsługuje grafy z setkami tysięcy krawędzi.
Uwaga na wagi krawędzi
Dijkstra nie działa poprawnie dla ujemnych krawędzi, ponieważ pobrana odległość może nie być ostateczna. W takim przypadku należy użyć algorytmu Bellmana-Forda.
Krótki test
Wykonano pop (d, u), ale d jest większe od dist[u]. Co należy zrobić?
Podsumowanie: Dijkstra z kopcem
Inicjalizuje się odległości, umieszcza (dist, node) w kopcu, pobiera najbliższy wierzchołek, pomija nieaktualne elementy i wykonuje relaksację sąsiadów. To algorytm Dijkstra o złożoności O((V+E) log V). 🚀
Często zadawane pytania
Czy lekcja „Algorytm Dijkstry ze stosem kopcowym” jest bezpłatna?
Tak — pełny tekst „Algorytm Dijkstry ze stosem kopcowym” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Algorytm Dijkstry ze stosem kopcowym”?
Zachłanne znajdowanie najkrótszych ścieżek po krawędziach nieujemnych Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 1 z 4.
Ile czasu zajmuje lekcja „Algorytm Dijkstry ze stosem kopcowym”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Algorytm Dijkstry ze stosem kopcowym
- 0-1 BFS z deque
- Bellman-Ford i ujemne krawędzie
- Floyd-Warshall dla wszystkich par