Ga naar hoofdinhoud

Bouwsteen 6 — herhaal tot klaar

Hier bouw je op verder

Leerdoel: je zet een lus om je ronde, zodat hij zichzelf herhaalt tot alle nodes bezocht zijn.

Wat we willen​

Blijf rondes doen tot er geen onbezochte node meer over is. In Python is dat een while-lus met een stopvoorwaarde.

Wanneer stoppen?​

kies_volgende geeft None terug als alles bezocht is. Dat is het stopsignaal:

while True:
    huidige = kies_volgende(afstanden, bezocht)
    if huidige is None:
        break                         # niemand meer over → klaar
    bezocht.add(huidige)
    for buur, gewicht in graph[huidige]:
        nieuwe = afstanden[huidige] + gewicht
        if nieuwe < afstanden[buur]:
            afstanden[buur] = nieuwe

while True is een lus zonder eigen stopvoorwaarde: hij draait tot iets erin break zegt, en dat is hier de enige uitgang. huidige is None vraagt of kies_volgende niemand teruggaf — None is wat die functie geeft als alles bezocht is, zoals je in bouwsteen 4 zag.

Waarom geen "for node in graph"?​

Dit lijkt op het eerste gezicht ook te kunnen:

for node in graph:
    # doe een ronde voor node

Maar dan kies je de nodes in de volgorde van de dict, en Dijkstra wil elke ronde de node met de laagste afstand. Die keuze maakt kies_volgende.

Stopt deze lus altijd?​

Ja. Elke ronde komt er precies één node bij in bezocht, dus na hoogstens len(graph) rondes zit iedereen erin. kies_volgende geeft dan None, en break springt eruit.

Elke ronde maakt bezocht één groter, en kies_volgende kijkt daar elke ronde naar. Dat is de hele garantie.

Voorspel​

Wat denk je dat de eindafstanden zijn voor onze mini-graph, start A?

Antwoord
{'A': 0, 'B': 4, 'C': 2, 'D': 5}

Wat je op papier ook kreeg.

Run​

Python
Code-omgeving wordt voorbereid…
Verwachte uitvoer
Ronde — bezoek A (afstand 0)
Ronde — bezoek C (afstand 2)
Ronde — bezoek B (afstand 4)
Ronde — bezoek D (afstand 5)

Klaar! Afstanden vanaf A: {'A': 0, 'B': 4, 'C': 2, 'D': 5}

Vier rondes, één per node, en dezelfde volgorde als op papier.

Wat nu nog mist​

Niets meer: dit is Dijkstra. Op de volgende pagina staat alles in één functie, zodat je het hele algoritme in één keer ziet.

Door naar het complete algoritme →.