Cheatsheet — Dijkstra
Klap open wat je nodig hebt.
Het algoritme zelf
De canonieke implementatie (afstanden + voorgangers)
def kies_volgende(afstanden, bezocht):
beste_node = None
kleinste = float('inf')
for node, d in afstanden.items():
if node in bezocht:
continue
if d < kleinste:
kleinste = d
beste_node = node
return beste_node
def dijkstra(graph, start):
afstanden = {}
for node in graph:
afstanden[node] = float('inf')
afstanden[start] = 0
bezocht = set()
voorgangers = {}
while True:
huidige = kies_volgende(afstanden, bezocht)
if huidige is None:
break
bezocht.add(huidige)
for buur, gewicht in graph[huidige]:
nieuwe = afstanden[huidige] + gewicht
if nieuwe < afstanden[buur]:
afstanden[buur] = nieuwe
voorgangers[buur] = huidige
return afstanden, voorgangers
Pad reconstrueren van start naar doel
def reconstrueer_pad(voorgangers, start, doel):
pad = []
huidige = doel
while huidige is not None:
pad.append(huidige)
if huidige == start:
break
huidige = voorgangers.get(huidige)
pad.reverse()
if pad and pad[0] == start:
return pad
return []
[] betekent: doel is onbereikbaar vanuit start.
De bouwstenen
1. Graph als adjacency-dict
graph = {
'A': [('B', 4), ('C', 2)],
'B': [('A', 4), ('D', 1)],
'C': [('A', 2), ('D', 8)],
'D': [('B', 1), ('C', 8)],
}
Elke verbinding twee keer in een niet-gerichte graph.
2. Afstanden + bezocht initialiseren
afstanden = {}
for node in graph:
afstanden[node] = float('inf')
afstanden[start] = 0
bezocht = set()
float('inf') betekent "nog niet gevonden"; elke route die je vindt is
er vanzelf een verbetering op.
3. Relax (één node's buren)
for buur, gewicht in graph[huidige]:
nieuwe = afstanden[huidige] + gewicht
if nieuwe < afstanden[buur]:
afstanden[buur] = nieuwe
Is de route via mij korter, dan bijwerken.
4. Kies volgende node
def kies_volgende(afstanden, bezocht):
beste_node = None
kleinste = float('inf')
for node, d in afstanden.items():
if node in bezocht:
continue
if d < kleinste:
kleinste = d
beste_node = node
return beste_node
Lineair zoeken naar minimum, met bezocht als filter. None als alles
bezocht is.
5+6. Een ronde + de lus
while True:
huidige = kies_volgende(afstanden, bezocht)
if huidige is None:
break
bezocht.add(huidige)
for buur, gewicht in graph[huidige]:
nieuwe = afstanden[huidige] + gewicht
if nieuwe < afstanden[buur]:
afstanden[buur] = nieuwe
Markeer vóór je opnieuw kiest; de relax-lus kijkt niet naar bezocht.
Eigenschappen
Wat werkt en wat niet?
| Werkt op | Werkt niet op |
|---|---|
| Niet-gerichte graphs | Negatieve gewichten |
| Gerichte graphs | "Beloningen" die door negatieve som korter maken |
| Positieve gewichten (afstand, tijd, kosten) | — |
| Gewogen én ongewogen (gewicht = 1) | — |
Voor negatieve gewichten → Bellman-Ford.
Complexiteit
| Versie | Per ronde | Totaal |
|---|---|---|
Onze versie (lineair kies_volgende) | O(V) | O(V²) |
| Met priority queue (heap) | O(log V) | O((V + E) log V) |
Voor kleine graphs is O(V²) goed genoeg en makkelijker te lezen. Wat
die termen betekenen staat bij Big O notatie.
Top-3 valkuilen
Veelgemaakte fouten
- Edges maar één kant op in niet-gerichte graph → onbereikbare nodes.
bezocht.add()vergeten → oneindige lus.- Negatieve gewichten → stille fout, antwoord klopt niet.
Volledig overzicht: er gaat iets mis.
Verder lezen
- wat is een graph?, voor wie de woorden nog eens wil.
- met pen en papier, voor wie het algoritme nog niet ziet.
- het complete algoritme, alles samen met de tekening.
- Big O — logaritmisch, waarom een priority queue helpt.