De kortste route — Dijkstra op papier

Zeven plekken, tien wegen. Jij bent het navigatiesysteem: je voert Dijkstra's algoritme uit met potlood en papier, en ontdekt dat de kortste route er heel anders uitziet dan je zou gokken.

Wat je nodig hebt

• Een geprinte hand-out per tweetal.
• Potlood en gum (je gaat afstanden doorstrepen en verbeteren).
• Ongeveer 20 minuten.

Gok eerst

Kijk 30 seconden naar de kaart hieronder en schrijf op, zonder te rekenen, welke route van A naar F volgens jou het kortst is en hoe lang die is:

Mijn gok: A → ____________________ → F, totale lengte: ______

Straks check je of je gelijk had.

De kaart

        2         8
   A ─────── B ─────── D
   │       ╱         ╱ │
   6     2         2   4
   │   ╱         ╱     │
   C ─── 3 ─── E ──7── F
                ╲      │
                 4     1
                  ╲    │
                   G ──┘

Tien wegen, elk met een lengte:

weg	lengte	weg	lengte
A─B	2	D─E	2
A─C	6	D─F	4
B─C	2	E─F	7
B─D	8	E─G	4
C─E	3	F─G	1

De spelregels

Drie stappen. De eerste doe je één keer, de andere twee herhaal je tot elke plek is afgevinkt:

0. Begin: schrijf in de kolom "start" bij A een 0 en bij elke andere plek een ?. Niets is afgevinkt.
1. Kies: pak van de nog níet afgevinkte plekken die met de laagste afstand. Vink hem af — deze afstand staat nu vast.
2. Reken: bekijk elke buur van de gekozen plek. Reken uit: afstand van de gekozen plek + lengte van de weg naar die buur. Is dat lager dan wat de buur nu heeft (of heeft de buur nog ?)? Streep door en schrijf het nieuwe getal op. Zet in de laatste kolom, via, de plek waar je vandaan kwam — die streep je dus ook door als je het getal verbetert.

Werk in tweetallen: één van jullie kiest en vinkt af, de ander rekent de buren door. Wissel elke ronde van rol.

De tabel

Vul per ronde de nieuwe stand in. Zet een vinkje bij de plek die je in die ronde afvinkt; een afgevinkte plek verandert daarna nooit meer. In de laatste kolom houd je bij vanaf welke plek die afstand kwam.

plek	start	ronde 1	ronde 2	ronde 3	ronde 4	ronde 5	ronde 6	ronde 7	via
A
B
C
D
E
F
G

Bespreek na

• Klopte je gok voor de route naar F? De meeste mensen zitten ernaast.
• Hoe vaak is de afstand van F doorgestreept en verbeterd? En hoe vaak zijn "via" van F?
• Lees de route naar F terug: kijk bij F wie zijn "via" is, ga naar die rij, en zo door tot je bij A bent. Welke route komt eruit?
• Waarom mag een afgevinkte plek nooit meer veranderen? (Hint: kan een route via een plek met een hógere afstand ooit korter uitpakken?)

Antwoorden

Deze pagina print als losse laatste pagina — houd hem achter de hand of knip hem eraf.

Stand na het begin en aan het eind van elke ronde (✓ = afgevinkt, daarna verandert de rij niet meer):

plek	start	ronde 1	ronde 2	ronde 3	ronde 4	ronde 5	ronde 6	ronde 7	via
A	0	0 ✓	—	—	—	—	—	—	—
B	?	2	2 ✓	—	—	—	—	—	A
C	?	6	4	4 ✓	—	—	—	—	B
D	?	?	10	10	9	9 ✓	—	—	E
E	?	?	?	7	7 ✓	—	—	—	C
F	?	?	?	?	14	13	12	12 ✓	G
G	?	?	?	?	11	11	11 ✓	—	E

Let op: in ronde 5 en 6 hebben D en G allebei nog niet-afgevinkte buren, dus de volgorde kiezen gaat op afstand: D (9) vóór G (11).

De kolom "via" staat er zoals hij aan het eind hoort te zijn. Bij F is hij onderweg twee keer doorgestreept, net als zijn afstand: eerst E (14), toen D (13), uiteindelijk G (12). Wie zijn tabel netjes bijhield, heeft daar drie namen boven elkaar staan.

Die laatste kolom is de hele route, achterstevoren. F kwam via G, G via E, E via C, C via B, B via A: lees terug en je hebt A → B → C → E → G → F.

De kortste routes vanuit A:

plek	afstand	route
B	2	A → B
C	4	A → B → C
D	9	A → B → C → E → D
E	7	A → B → C → E
F	12	A → B → C → E → G → F
G	11	A → B → C → E → G

De route naar F gebruikt vijf wegen en komt toch op 12 uit, korter dan de routes die er logisch uitzien: A → B → D → F (14) of A → C → E → F (16). F werd onderweg twee keer verbeterd, van 14 naar 13 naar 12.

Verder op de site

• Dijkstra — het idee
• Doe het met pen en papier — dezelfde methode, voorgedaan op een kleinere kaart
• Bouwsteen 1 — de graph in Python — hetzelfde algoritme in Python bouwen