0Pricing
DSA Interview Prep · Lekcja

Algorytm Dijkstry z kolejką priorytetową

Implementować algorytm Dijkstry za pomocą heapq, prześledzić kroki relaksacji na grafie ważonym oraz rozwiązać problem najtańszych lotów z maksymalnie k przesiadkami

Algorytm Dijkstry z kolejką priorytetową to bezpłatna lekcja DSA 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 DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.

Najkrótsza ścieżka w grafach ważonych

Algorytm Dijkstry znajduje najkrótszą ścieżkę z pojedynczego wierzchołka źródłowego do wszystkich pozostałych wierzchołków w grafie ważonym o nieujemnych wagach krawędzi. Działa, przetwarzając zachłannie wierzchołki w kolejności ich obecnie znanych najlepszych odległości — zawsze rozwija najbliższy nieodwiedzony wierzchołek. Kluczową strukturą danych jest kopiec minimum (kolejka priorytetowa), który efektywnie zwraca wierzchołek o najmniejszej odległości.

Przegląd kroków algorytmu

Algorytm Dijkstry: (1) należy zainicjalizować dist[source] = 0 oraz dist[all others] = inf; (2) umieścić (0, source) w kopcu minimum; (3) pobrać wierzchołek u o najmniejszej odległości. Jeśli został już odwiedzony z mniejszą odległością, należy go pominąć; (4) dla każdego sąsiada v wierzchołka u: jeśli dist[u] + weight(u,v) < dist[v], należy zaktualizować dist[v] i dodać (dist[v], v) do kopca; (5) powtarzać te kroki, dopóki kopiec nie będzie pusty.

Implementacja w języku Python z użyciem heapq

Moduł heapq języka Python implementuje kopiec minimum. Graf reprezentujemy za pomocą listy sąsiedztwa: graph[u] = [(v, weight), ...]. Kopiec przechowuje krotki (distance, node). Używamy zbioru visited, aby pomijać nieaktualne wpisy w kopcu — wpisy dodane, zanim znaleziono lepszą ścieżkę.

import heapq

def dijkstra(graph, source):
    n = len(graph)
    dist = [float('inf')] * n
    dist[source] = 0
    heap = [(0, source)]  # (distance, node)
    visited = set()
    
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        
        for v, weight in graph[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(heap, (dist[v], v))
    
    return dist

Przykład z rozwiązaniem

Rozważmy graf z 5 wierzchołkami i krawędziami: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). Najkrótsze ścieżki z wierzchołka 0: do 1 przez 0→2→1 mają koszt 3, do 2 koszt 1, do 3 przez 0→2→1→3 koszt 4, a do 4 przez 0→2→1→3→4 koszt 7. Algorytm Dijkstry znajduje wszystkie te ścieżki podczas jednego przebiegu, a nie tylko ścieżkę do pojedynczego celu.

import heapq

def dijkstra(graph, source):
    dist = [float('inf')] * len(graph)
    dist[source] = 0
    heap = [(0, source)]
    visited = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited:
            continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

graph = [
    [(1,4),(2,1)],  # 0
    [(3,1)],         # 1
    [(1,2),(3,5)],   # 2
    [(4,3)],         # 3
    []               # 4
]
print(dijkstra(graph, 0))  # [0, 3, 1, 4, 7]

Dlaczego algorytm Dijkstry nie działa dla ujemnych wag

Poprawność algorytmu Dijkstry opiera się na założeniu, że gdy wierzchołek zostanie zdjęty z kopca minimalnego, jego odległość jest ostateczna. Jest to prawdą wyłącznie wtedy, gdy wagi krawędzi są nieujemne. W przypadku ujemnej krawędzi u→v o wadze -5 po odwiedzeniu v możemy znaleźć krótszą ścieżkę przechodzącą przez u — ale v zostało już oznaczone jako odwiedzone. Pojedyncza ujemna krawędź może unieważnić wszystkie dalsze obliczenia odległości.

Najtańsze loty z maksymalnie K przesiadkami (LeetCode 787)

Ten problem wprowadza dodatkowe ograniczenie: maksymalnie k przesiadek. Standardowy algorytm Dijkstry nie obsługuje natywnie liczby kroków. Rozwiązanie polega na rozszerzeniu stanu do postaci (cost, node, stops_remaining). Należy zastosować algorytm Dijkstry z tą 3-elementową krotką albo użyć algorytmu Bellmana-Forda z k+1 przebiegami relaksacji. Zmodyfikowany algorytm Dijkstry kończy działanie, gdy stops_remaining osiągnie 0, co zapobiega dalszym przejściom.

import heapq
from collections import defaultdict

def findCheapestPrice(n, flights, src, dst, k):
    graph = defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))
    
    heap = [(0, src, k + 1)]  # (cost, node, hops_left)
    visited = {}  # node -> min hops_left seen at this cost level
    
    while heap:
        cost, node, hops = heapq.heappop(heap)
        if node == dst:
            return cost
        if hops == 0:
            continue
        if visited.get(node, 0) >= hops:
            continue
        visited[node] = hops
        for nxt, w in graph[node]:
            heapq.heappush(heap, (cost + w, nxt, hops - 1))
    return -1

print(findCheapestPrice(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1))  # 200

Analiza złożoności czasowej

W przypadku kopca binarnego algorytm Dijkstry działa w czasie O((V + E) log V): każdy wierzchołek jest zdejmowany raz (V operacji zdjęcia), każda krawędź może spowodować dodanie elementu do kopca (E operacji dodania), a każda operacja na kopcu kosztuje O(log V). W przypadku kopca Fibonacciego ograniczenie poprawia się do O(E + V log V), ale Pythonowy heapq jest kopcem binarnym. Dla grafów rzadkich (E ≈ V) wersja z kopcem binarnym ma złożoność O(V log V), a dla grafów gęstych (E ≈ V²) — O(V² log V).

Odtwarzanie najkrótszej ścieżki

Aby odzyskać rzeczywistą ścieżkę (a nie tylko odległości), należy utrzymywać tablicę prev: podczas aktualizowania dist[v] ustawić prev[v] = u. Po zakończeniu działania algorytmu należy odtworzyć ścieżkę od źródła do celu, śledząc wskaźniki prev wstecz: rozpocząć od dst, podążać za wskaźnikami prev aż do source, a następnie odwrócić wynik.

import heapq

def dijkstra_path(graph, source, target):
    n = len(graph)
    dist = [float('inf')] * n
    prev = [-1] * n
    dist[source] = 0
    heap = [(0, source)]
    visited = set()
    while heap:
        d, u = heapq.heappop(heap)
        if u in visited: continue
        visited.add(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(heap, (dist[v], v))
    # Reconstruct
    path, node = [], target
    while node != -1:
        path.append(node)
        node = prev[node]
    return dist[target], path[::-1]

Używanie słownika w grafach rzadkich

Gdy wierzchołki są napisami lub niekolejnymi liczbami całkowitymi, należy użyć defaultdict(list) jako listy sąsiedztwa oraz zwykłego dict do przechowywania odległości. Jest to częste w zadaniach LeetCode, takich jak Network Delay Time, w których wierzchołki są oznaczone liczbami od 1 do n. Należy pamiętać o użyciu dist = {node: inf for node in all_nodes} i sprawdzeniu, które wierzchołki są nieosiągalne po zakończeniu działania algorytmu.

import heapq
from collections import defaultdict

def networkDelayTime(times, n, k):
    graph = defaultdict(list)
    for u, v, w in times:
        graph[u].append((v, w))
    
    dist = {i: float('inf') for i in range(1, n+1)}
    dist[k] = 0
    heap = [(0, k)]
    
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    
    ans = max(dist.values())
    return ans if ans < float('inf') else -1

print(networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2))  # 2

Porównanie z BFS dla grafów nieważonych

W przypadku grafów nieważonych BFS znajduje najkrótsze ścieżki w czasie O(V + E) — szybciej niż algorytm Dijkstry o złożoności O((V+E) log V). Algorytm Dijkstry uogólnia BFS na grafy ważone, używając kolejki priorytetowej zamiast zwykłej kolejki FIFO. Gdy wszystkie wagi krawędzi są równe, algorytm Dijkstry sprowadza się do BFS. Należy wybrać BFS dla grafów nieważonych, algorytm Dijkstry dla nieujemnych wag oraz algorytm Bellmana-Forda dla ujemnych wag.

Dijkstra z optymalizacją decrease-key

Podręcznikowa wersja algorytmu Dijkstry używa kolejki priorytetowej z operacją decrease-key: gdy odległość wierzchołka ulega poprawie, jego priorytet jest aktualizowany w miejscu. Wymaga to kopca Fibonacciego, aby osiągnąć O(E + V log V), ale jest trudne w implementacji. Stosowane podczas rozmów rekrutacyjnych leniwe usuwanie polega na dodaniu nowego elementu i pomijaniu nieaktualnych elementów zdejmowanych z kopca — jest prostsze i wiąże się tylko ze stałym narzutem. W Pythonie leniwe usuwanie z użyciem heapq jest standardową implementacją używaną podczas rozmów rekrutacyjnych.

Szybki sprawdzian

Sprawdź swoje zrozumienie zagadnień z kursu Data Structures & Algorithms — Coding Interview Prep przedstawionych w tej lekcji.

Podsumowanie lekcji

W tej lekcji poznali Państwo następujące informacje: algorytm Dijkstry używa kopca minimalnego do zachłannego przetwarzania wierzchołków w kolejności ich aktualnie najlepszych odległości, działa w czasie O((V+E) log V) i nie działa dla krawędzi o ujemnych wagach, a nieaktualne wpisy w kopcu są obsługiwane przez sprawdzanie zbioru visited podczas zdejmowania elementu. Następnie omówimy algorytm Bellmana-Forda, który obsługuje ujemne wagi dzięki V-1 przebiegom relaksacji.

Często zadawane pytania

Czy lekcja „Algorytm Dijkstry z kolejką priorytetową” jest bezpłatna?

Tak — pełny tekst „Algorytm Dijkstry z kolejką priorytetową” 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 DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Algorytm Dijkstry z kolejką priorytetową”?

Implementować algorytm Dijkstry za pomocą heapq, prześledzić kroki relaksacji na grafie ważonym oraz rozwiązać problem najtańszych lotów z maksymalnie k przesiadkami Ćwiczysz DSA 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ąć DSA Interview Prep?

Nie wymagamy żadnego doświadczenia. DSA 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 z kolejką priorytetową”?

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 DSA Interview Prep?

Tak. Każda lekcja DSA 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

  1. Algorytm Dijkstry z kolejką priorytetową
  2. Bellman-Ford i cykle ujemne
  3. Floyd-Warshall: najkrótsze ścieżki między wszystkimi parami wierzchołków
  4. Opóźnienie sieci i odtwarzanie ścieżki
← Powrót do DSA Interview Prep