Dijkstra's algoritme met een priority queue
Implementeer Dijkstra met heapq, doorloop de relaxatiestappen op een gewogen graaf en los cheapest-flights-within-k-stops op.
Dijkstra's algoritme met een priority queue is een gratis DSA Interview Prep-les op CoddyKit. Dit is les 1 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject DSA Interview Prep. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Kortste paden in gewogen grafen
Het algoritme van Dijkstra vindt het kortste pad van één bronknooppunt naar alle andere knooppunten in een gewogen graaf met niet-negatieve kantgewichten. Het werkt door knooppunten gulzig te verwerken in de volgorde van hun momenteel best bekende afstand: steeds wordt het dichtstbijzijnde nog niet bezochte knooppunt uitgebreid. De belangrijkste datastructuur is een min-heap (prioriteitswachtrij), waarmee je efficiënt het knooppunt met de kleinste afstand ophaalt.
Overzicht van de algoritmestappen
Het algoritme van Dijkstra: (1) initialiseer dist[source] = 0 en dist[all others] = inf. (2) Plaats (0, source) in een min-heap. (3) Haal het knooppunt u met de kleinste afstand eruit. Als het al met een kleinere afstand is bezocht, sla het dan over. (4) Controleer voor elke buur v van u: als dist[u] + weight(u,v) < dist[v], werk je dist[v] bij en plaats je (dist[v], v) in de heap. (5) Herhaal dit totdat de heap leeg is.
Python-implementatie met heapq
Python's heapq implementeert een min-heap. We stellen de graaf voor als een aangrenzingslijst: graph[u] = [(v, weight), ...]. De heap bevat tupels van het type (distance, node). We gebruiken een verzameling visited om verouderde heap-vermeldingen over te slaan — vermeldingen die zijn toegevoegd voordat er een beter pad werd gevonden.
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 distUitgewerkt voorbeeld
Beschouw een graaf met 5 knooppunten en de kanten: 0→1 (4), 0→2 (1), 2→1 (2), 1→3 (1), 2→3 (5), 3→4 (3). De kortste paden vanaf knooppunt 0 zijn: naar 1 via 0→2→1 met kosten 3, naar 2 met kosten 1, naar 3 via 0→2→1→3 met kosten 4 en naar 4 via 0→2→1→3→4 met kosten 7. Dijkstra vindt al deze paden in één doorloop, niet alleen het pad naar één doelknooppunt.
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]Waarom Dijkstra faalt bij negatieve gewichten
De correctheid van Dijkstra berust op het feit dat de afstand van een knoop definitief is zodra die uit de min-heap wordt gehaald. Dit geldt alleen als de gewichten van de kanten niet-negatief zijn. Bij een negatieve kant u→v met gewicht -5 kunnen we na het bezoeken van v een korter pad via u vinden — maar v is dan al als bezocht gemarkeerd. Eén negatieve kant kan alle daaropvolgende afstandsberekeningen ongeldig maken.
Goedkoopste vluchten met maximaal K tussenstops (LeetCode 787)
Dit probleem voegt een beperking toe: maximaal k tussenstops. Standaard-Dijkstra verwerkt aantallen stappen niet van zichzelf. Oplossing: breid de toestand uit naar (cost, node, stops_remaining). Gebruik Dijkstra met deze 3-tupel, of gebruik Bellman-Ford met k+1 relaxatierondes. De aangepaste versie van Dijkstra stopt zodra stops_remaining 0 bereikt, zodat er geen verdere sprongen worden gemaakt.
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)) # 200Analyse van tijdcomplexiteit
Met een binaire heap werkt Dijkstra in O((V + E) log V)-tijd: elke knoop wordt één keer uit de heap gehaald (V verwijderingen), elke kant kan een toevoeging veroorzaken (E toevoegingen) en elke heapbewerking kost O(log V). Met een Fibonacci-heap wordt de bovengrens O(E + V log V), maar heapq van Python is een binaire heap. Voor ijle grafen (E ≈ V) is de versie met een binaire heap O(V log V); voor dichte grafen (E ≈ V²) is die O(V² log V).
Het kortste pad reconstrueren
Als je het daadwerkelijke pad wilt terugvinden, en niet alleen de afstanden, houd je een prev-array bij: stel bij het bijwerken van dist[v] prev[v] = u in. Reconstrueer na afloop van het algoritme het pad van bron naar bestemming door terug te lopen: begin bij dst, volg de verwijzingen in prev tot je bij source bent en keer het resultaat om.
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]Een dict gebruiken voor ijle grafen
Wanneer knopen tekenreeksen of niet-aaneengesloten gehele getallen zijn, gebruik je een defaultdict(list) voor de adjacentielijst en een gewone dict voor de afstanden. Dit komt vaak voor in LeetCode-problemen zoals Network Delay Time, waarin knopen de labels 1 tot en met n hebben. Vergeet niet dist = {node: inf for node in all_nodes} te gebruiken en na het algoritme te controleren welke knopen onbereikbaar zijn.
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)) # 2Vergelijking met BFS voor ongewogen grafen
Voor ongewogen grafen vindt BFS kortste paden in O(V + E) — sneller dan O((V+E) log V) van Dijkstra. Dijkstra veralgemeniseert BFS naar gewogen grafen door een prioriteitswachtrij te gebruiken in plaats van een gewone FIFO-wachtrij. Wanneer alle gewichten van de kanten gelijk zijn, ontaardt Dijkstra in BFS. Kies BFS voor ongewogen grafen, Dijkstra voor niet-negatieve gewichten en Bellman-Ford voor negatieve gewichten.
Dijkstra met decrease-key-optimalisatie
De Dijkstra-versie uit studieboeken gebruikt een prioriteitswachtrij met decrease-key: wanneer de afstand van een knoop verbetert, werk je de prioriteit direct bij. Hiervoor is een Fibonacci-heap nodig om O(E + V log V) te bereiken, maar die is lastig te implementeren. Bij de aanpak met luie verwijdering die in sollicitatiegesprekken wordt gebruikt, voeg je in plaats daarvan een nieuwe invoer toe en sla je verouderde verwijderingen over — eenvoudiger, met slechts een constante factor extra werk. In Python is luie verwijdering met heapq de standaardimplementatie voor sollicitatiegesprekken.
Korte toets
Toets je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep uit deze les.
Samenvatting van de les
In deze les heb je geleerd: Dijkstra gebruikt een min-heap om knopen hebzuchtig te verwerken in volgorde van hun huidige beste afstand, het algoritme werkt in O((V+E) log V)-tijd en faalt bij kanten met negatieve gewichten en verouderde heap-invoeren worden afgehandeld door bij het verwijderen een bezochte-verzameling te controleren. Hierna behandelen we Bellman-Ford, dat negatieve gewichten verwerkt met n-1 relaxatierondes.
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Dijkstra's algoritme met een priority queue” gratis?
Ja — je kunt hier op het web alle 3 lessen van het leerpad DSA Interview Prep, waaronder “Dijkstra's algoritme met een priority queue”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Wat leer ik in “Dijkstra's algoritme met een priority queue”?
Implementeer Dijkstra met heapq, doorloop de relaxatiestappen op een gewogen graaf en los cheapest-flights-within-k-stops op. Je oefent met DSA Interview Prep door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met DSA Interview Prep te beginnen?
Ervaring vooraf is niet nodig. DSA Interview Prep op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.
Hoe lang duurt de les “Dijkstra's algoritme met een priority queue”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over DSA Interview Prep?
Ja. Elke les over DSA Interview Prep bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Dijkstra's algoritme met een priority queue
- Bellman-Ford en negatieve cycli
- Floyd-Warshall: kortste paden tussen alle paren
- Network Delay Time en padreconstructie