Doe het met pen en papier

Leerdoel: je begrijpt hoe Dijkstra werkt door hem zelf stap voor stap uit te voeren. Geen code, alleen een tabel die je bijwerkt, en je ziet een afstand meer dan eens beter worden terwijl je verder zoekt.

Onze mini-graph

                1
       A ─────────── C
       │         ╱   │   ╲
       │       2     3     5
       6     ╱       │       ╲
       │   ╱         │         ╲
       B ─────────── D ─── 1 ── E
              2

Vijf nodes, A tot en met E, en zeven verbindingen. De vraag: vanuit A, wat is de kortste afstand naar elke andere node?

Lees het plaatje:

• A─C heeft gewicht 1 (de bovenste edge).
• A─B heeft gewicht 6 (de linker edge).
• B─C heeft gewicht 2 (de diagonaal).
• B─D heeft gewicht 2 (onder).
• C─D heeft gewicht 3 (middenverticaal).
• C─E heeft gewicht 5 (de rechter-diagonaal).
• D─E heeft gewicht 1 (rechtsonder).

Stap 0 — de tabel klaarzetten

Dijkstra houdt drie dingen bij. Pak een vel papier en teken deze tabel:

node	kortste afstand bekend?	huidige beste afstand
A	nee	0
B	nee	?
C	nee	?
D	nee	?
E	nee	?

• Bekend? zegt of we de kortste afstand al definitief weten. Aan het begin is dat nergens zo.
• Huidige beste afstand is ons beste vermoeden tot nu toe. Alles begint op ?, nog onbekend, behalve de start: die staat op 0, want daar zijn we al.

Dit is stap 0, en die doe je één keer. Zonder die 0 bij de start is er in ronde 1 niets te kiezen: alles zou ? zijn.

De gouden regel

Stap 0: zet elke afstand op ?, behalve de start: die krijgt 0. Niemand is bekend.

Stap A: pak onder de "nog niet bekend" rijen die met de laagste afstand. Markeer hem als bekend.

Stap B: kijk naar zijn buren. Voor elke buur, reken uit: "afstand van mij + gewicht naar buur". Is dat kleiner dan wat de buur nu heeft? Update.

Stap 0 doe je één keer. Stap A en B herhaal je tot er geen "nog niet bekend" rijen meer zijn.

Ronde 1 — start vanaf A

Stap A — Wie heeft de laagste afstand onder de nog-niet-bekende?

Dat is A met afstand 0. Markeer A als bekend:

node	bekend?	afstand
A	ja ✓	0
B	nee	?
C	nee	?
D	nee	?
E	nee	?

Stap B — A's buren.

A heeft twee buren: B (gewicht 6) en C (gewicht 1).

• B: kandidaat = 0 + 6 = 6. Was ? → update naar 6.
• C: kandidaat = 0 + 1 = 1. Was ? → update naar 1.

node	bekend?	afstand
A	ja ✓	0
B	nee	6
C	nee	1
D	nee	?
E	nee	?

Ronde 2 — kies C, en pas op

Stap A — Laagste onder nog-niet-bekend?

C met 1 wint van B met 6, D met ? en E met ?. Markeer als bekend:

node	bekend?	afstand
A	ja ✓	0
B	nee	6
C	ja ✓	1
D	nee	?
E	nee	?

Stap B — C's buren.

C heeft vier buren: A (1), B (2), D (3), E (5).

• A: kandidaat = 1 + 1 = 2. A is al 0 → niet beter, niets doen.
• B: kandidaat = 1 + 2 = 3. Was 6 → 3 is veel beter, update.
• D: kandidaat = 1 + 3 = 4. Was ? → update naar 4.
• E: kandidaat = 1 + 5 = 6. Was ? → update naar 6.

node	bekend?	afstand
A	ja ✓	0
B	nee	3 ⬇
C	ja ✓	1
D	nee	4
E	nee	6

B is opeens een stuk korter. Eerst dachten we 6, de directe weg A→B, maar via C blijkt het 3 te zijn (A→C→B). Daar draait Dijkstra om: niet stoppen bij je eerste schatting.

Ronde 3 — kies B, niets verbetert

Stap A — Laagste onder nog-niet-bekend?

B met 3 wint van D (4) en E (6):

node	bekend?	afstand
A	ja ✓	0
B	ja ✓	3
C	ja ✓	1
D	nee	4
E	nee	6

Stap B — B's buren.

B heeft drie buren: A (6), C (2), D (2).

• A: 3 + 6 = 9. Al 0 → niets doen.
• C: 3 + 2 = 5. Al 1 → niets doen.
• D: 3 + 2 = 5. Huidige 4 → 5 is niet beter, niets doen.

Tabel niet veranderd:

node	bekend?	afstand
A	ja ✓	0
B	ja ✓	3
C	ja ✓	1
D	nee	4
E	nee	6

Een ronde zonder updates is ook normaal. Dijkstra kijkt naar iedere buur, ook als het niks oplevert.

Ronde 4 — kies D, en weer een verbetering

Stap A — Laagste onder nog-niet-bekend?

D met 4 wint van E met 6:

node	bekend?	afstand
A	ja ✓	0
B	ja ✓	3
C	ja ✓	1
D	ja ✓	4
E	nee	6

Stap B — D's buren.

D heeft drie buren: B (2), C (3), E (1).

• B: 4 + 2 = 6. Al 3 → niets doen.
• C: 4 + 3 = 7. Al 1 → niets doen.
• E: 4 + 1 = 5. Huidige 6 → 5 is beter, update.

node	bekend?	afstand
A	ja ✓	0
B	ja ✓	3
C	ja ✓	1
D	ja ✓	4
E	nee	5 ⬇

E was 6, via A→C→E. Maar via D is het A→C→D→E = 1 + 3 + 1 = 5. Drie korte stappen verslaan hier één lange. Goed dat we na ronde 2 niet gestopt zijn.

Ronde 5 — kies E, klaar

Stap A — Alleen E is nog over met afstand 5:

node	bekend?	afstand
A	ja ✓	0
B	ja ✓	3
C	ja ✓	1
D	ja ✓	4
E	ja ✓	5

Stap B — E's buren.

C (al 1) en D (al 4). Geen verbeteringen mogelijk.

Klaar

Alle nodes zijn bekend. Onze tabel:

node	kortste afstand vanuit A	bereikt via
A	0	(start)
B	3	A → C → B
C	1	A → C
D	4	A → C → D
E	5	A → C → D → E

De kolom "bereikt via" staat niet in je tabel; die heb ik afgelezen door bij elke update te onthouden vanaf welke node hij kwam. Hoe je dat in code doet, zie je bij pas aan.

Wat is hier opvallend?

• B werd één keer bijgewerkt, van 6 naar 3. De omweg via C is de helft van de directe weg.
• E werd ook één keer bijgewerkt, van 6 naar 5, en dat gebeurde pas drie rondes nadat we hem voor het eerst zagen.
• Alle kortste routes lopen via C. Dat raad je op het oog niet.
• Geen enkele route is direct. De directe A→B bestaat wel (6), maar de omweg is korter.

Waarom werkt dit?

Elke keer dat we de laagste onder de nog-niet-bekende nodes als bekend markeren, kan zijn afstand niet meer beter worden. Een nieuwe route zou via een andere nog-niet-bekende node moeten lopen, en die heeft een afstand die niet lager is. Zo'n route wordt dus nooit korter.

Daarom mogen we hem klaar verklaren zonder er later spijt van te krijgen.

info

Wil je dit klassikaal doen op een grotere kaart, zonder scherm? Print de werkvorm De kortste route — Dijkstra op papier.

Probeer het zelf — een andere startnode

Doe Dijkstra op dezelfde graph, maar nu vanuit E als start. Welke afstanden krijg je naar A, B, C, D?

Antwoord

node	afstand vanuit E
A	5 (via D, C)
B	3 (via D)
C	4 (via D)
D	1 (direct)
E	0

Vanaf E is de directe E─C (gewicht 5) niet de kortste route naar C; via D is het 1 + 3 = 4. Weer twee updates onderweg.

Nu jij — de kleine graph uit de code-pagina's

De bouwstenen gebruiken een kleinere graph, zodat de code kort blijft. Doe Dijkstra er eerst op papier op, vanuit A, met dezelfde drie stappen, en houd je tabel daarna bij de hand: elke bouwsteen legt zijn uitvoer ernaast.

       4
   A ─────── B
   │         │
   2         1
   │         │
   C ─────── D
       8

Vier nodes, vier edges: A─B 4, A─C 2, B─D 1, C─D 8.

Antwoord

De stand na stap 0 en na elke ronde (✓ = in die ronde bekend gemarkeerd, daarna verandert de rij niet meer):

node	stap 0	ronde 1	ronde 2	ronde 3	ronde 4
A	0	0 ✓	—	—	—
B	?	4	4	4 ✓	—
C	?	2	2 ✓	—	—
D	?	?	10	5	5 ✓

Ronde 1 kiest A en geeft B 4 en C 2. Ronde 2 kiest C (2 is lager dan 4) en geeft D 2 + 8 = 10. Ronde 3 kiest B: via B is D 4 + 1 = 5, dus die zakt van 10 naar 5. Ronde 4 kiest D; alles is bekend.

Eindstand: A 0, B 4, C 2, D 5.

Tijd om dit in Python te bouwen

Je weet nu wat Dijkstra doet en waarom het werkt. Elke kolom van je tabel en elke stap van de gouden regel wordt nu een stukje Python, één per pagina.

De code-pagina's gebruiken de kleine graph die je net op papier deed. Het algoritme is hetzelfde; het voorbeeld is kleiner.

Door naar de stellingen →.