Bouwsteen 5 — doe één ronde

Leerdoel: je combineert kies volgende en relax tot precies één ronde van Dijkstra, zonder lus. Eén rij van je papieren tabel.

Wat we willen

Eén ronde doet drie dingen, in deze volgorde: kies de volgende node (de laagste afstand onder de niet-bezochte), markeer hem als bezocht, en relax al zijn buren.

huidige = kies_volgende(afstanden, bezocht)   # stap 1
bezocht.add(huidige)                           # stap 2
for buur, gewicht in graph[huidige]:           # stap 3
    nieuwe = afstanden[huidige] + gewicht
    if nieuwe < afstanden[buur]:
        afstanden[buur] = nieuwe

Meer is een ronde niet. De herhaling komt pas in bouwsteen 6.

Waarom markeren?

Stap 2 is de kortste regel van de drie, en de enige die kies_volgende ziet. Die functie slaat alles over wat in bezocht zit; wat er niet in zit kan volgende ronde opnieuw gekozen worden. Met het markeren zegt een ronde tegen de volgende: deze is af.

Voorspel

We starten met stap 0:

afstanden = {'A': 0, 'B': float('inf'), 'C': float('inf'), 'D': float('inf')}
bezocht = set()

Wat denk je dat afstanden en bezocht zijn na één ronde?

Antwoord

afstanden = {'A': 0, 'B': 4, 'C': 2, 'D': inf}
bezocht = {'A'}

De keuze valt op A: afstand 0, en niemand is bezocht. A gaat in bezocht, en zijn buren krijgen hun afstand: B 4 en C 2. Dat is ronde 1 van je papieren tabel.

Run — één ronde vanaf de start

Python

Code-omgeving wordt voorbereid…

Verwachte uitvoer

Kies: A
Bezocht: {'A'}
    update B → 4
    update C → 2
Afstanden: {'A': 0, 'B': 4, 'C': 2, 'D': inf}

Doe een tweede ronde

Hieronder staat de ronde in een functie, en die roepen we vier keer aan. Kijk hoe de tabel verder verandert:

Python

Code-omgeving wordt voorbereid…

Verwachte uitvoer

Ronde — kies A
    update B → 4
    update C → 2
    afstanden: {'A': 0, 'B': 4, 'C': 2, 'D': inf}

Ronde — kies C
    update D → 10
    afstanden: {'A': 0, 'B': 4, 'C': 2, 'D': 10}

Ronde — kies B
    update D → 5
    afstanden: {'A': 0, 'B': 4, 'C': 2, 'D': 5}

Ronde — kies D
    afstanden: {'A': 0, 'B': 4, 'C': 2, 'D': 5}

Dezelfde rondes als op je papieren tabel. In ronde 3 zakt D van 10 naar 5, omdat de route via B korter is dan die via C.

Wat nu nog mist

Vier keer ronde() typen is nog met de hand tellen. Een while-lus eromheen laat het algoritme zelf stoppen.

Door naar bouwsteen 6: de lus →.