8.14 Cheatsheet — Dijkstra
Snelle referentie. 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 = {node: float('inf') for node in graph}
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()
return pad if pad and pad[0] == start else []
[] 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 = {node: float('inf') for node in graph}
afstanden[start] = 0
bezocht = set()
float('inf') = "nog niet gevonden". Zo werkt elke gevonden route
automatisch als een verbetering.
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? Update."
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
Eerst markeren, dan relaxen.
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²) prima en duidelijker te lezen. Zie
Big O notatie voor een uitleg van die termen.
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: stap 13: er gaat iets mis.
Verder lezen
- stap 1: wat is een graph? — opnieuw door het concept.
- stap 2: met pen en papier — hand-trace voor wie het algoritme nog niet "ziet".
- stap 10: het complete algoritme — alles samen met visualisatie.
- Big O — logaritmisch — waarom een priority queue helpt.