Ga naar hoofdinhoud

Bouwsteen 4 — kies de volgende node

Hier bouw je op verder

Leerdoel: je vertaalt stap A van het papier naar Python: vind de node met de laagste afstand die nog niet bezocht is.

Wat we willen​

Op papier pakte je de laagste afstand onder de rijen die nog niet bekend waren. In Python loop je over afstanden, slaat over wie al in bezocht zit, en onthoudt wie de laagste heeft.

Het patroon — lineair zoeken naar minimum​

Dit is vind-maximum, maar dan het minimum, en met een filter.

beste_node = None
kleinste_afstand = float('inf')

for node, d in afstanden.items():
    if node in bezocht:
        continue                 # sla bezochten over
    if d < kleinste_afstand:
        kleinste_afstand = d
        beste_node = node

Drie regels doen het werk. if node in bezocht: continue slaat een node over die al klaar is. d < kleinste_afstand vervangt alleen bij echt kleiner. En beste_node begint op None: is alles bezocht, dan komt niemand door het filter en blijft het None. Dat is ons signaal dat we klaar zijn.

Voorspel​

Wat denk je dat dit print?

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

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

print(beste_node)
Antwoord
C

A wordt overgeslagen, die is al bezocht. Bij B is 4 kleiner dan oneindig, dus B wordt de beste met 4. Bij C is 2 kleiner dan 4, dus C neemt het over. Bij D is oneindig niet kleiner dan 2, dus er verandert niets. Het eind is C.

Run​

Python
Code-omgeving wordt voorbereid…

In een functie​

Dit gebeurt elke ronde opnieuw, dus het wordt een functie:

Python
Code-omgeving wordt voorbereid…
Verwachte uitvoer
A
C
B
None

Zonder bezochte nodes wint A met 0. Met A bezocht is C de laagste die overblijft, met A en C bezocht wint B, en met alles bezocht komt niemand door het filter: None, ons stopsignaal.

Wat nu nog mist​

De graph (bouwsteen 1), de tabel (2), relax (3) en kies volgende (4) staan er nu elk apart. Samen vormen ze één ronde van Dijkstra, één rij van je papieren tabel.

Door naar bouwsteen 5: doe één ronde →.