Ga naar hoofdinhoud

Bouwsteen 3 — update één buur (relax)

Hier bouw je op verder

Leerdoel: je vertaalt stap B van het papier naar Python: één buur bekijken en zijn afstand bijwerken als de route via mij korter is.

Wat we willen​

Op papier deed je dit voor elke buur:

Mijn afstand plus de stap naar de buur: is dat korter dan wat de buur nu heeft? Dan bijwerken.

Op de kleine graph, ronde 3: vanuit B (afstand 4) keek je naar buur D (gewicht 1). De kandidaat is 4 + 1 = 5, D had 10, dus D werd 5.

De formule​

nieuwe_afstand = afstanden[huidige] + gewicht
if nieuwe_afstand < afstanden[buur]:
    afstanden[buur] = nieuwe_afstand

Drie regels: een berekening, een vergelijking en een toewijzing. afstanden[huidige] is de afstand van de start tot waar we nu staan, gewicht is de stap naar deze buur, en nieuwe_afstand is wat de buur zou kosten als je via ons gaat.

Voorspel​

Wat denk je dat dit print?

afstanden = {'A': 0, 'B': 4, 'C': 2, 'D': 10}
huidige = 'B'
buur = 'D'
gewicht = 1

nieuwe_afstand = afstanden[huidige] + gewicht
if nieuwe_afstand < afstanden[buur]:
    afstanden[buur] = nieuwe_afstand

print(afstanden)
Antwoord
{'A': 0, 'B': 4, 'C': 2, 'D': 5}

nieuwe_afstand is 4 + 1 = 5. Dat is kleiner dan 10, dus afstanden['D'] wordt 5.

Run​

Python
Code-omgeving wordt voorbereid…

Wat als de buur al beter is?​

Hetzelfde, maar nu vanuit C (afstand 2) naar buur A (gewicht 2). De kandidaat is 2 + 2 = 4, en A heeft al 0. Dus niets.

Python
Code-omgeving wordt voorbereid…

Voor alle buren van een node​

Straks doe je dit per ronde voor alle buren tegelijk, met één for-lus over graph[huidige]:

huidige = 'A'
for buur, gewicht in graph[huidige]:
    nieuwe = afstanden[huidige] + gewicht
    if nieuwe < afstanden[buur]:
        afstanden[buur] = nieuwe

Vanaf A (afstand 0) krijgen B en C zo in één lus hun afstand.

Python
Code-omgeving wordt voorbereid…
Verwachte uitvoer
Voor: {'A': 0, 'B': inf, 'C': inf, 'D': inf}
    update B → 4
    update C → 2
Na:   {'A': 0, 'B': 4, 'C': 2, 'D': inf}

Dat is ronde 1 van je papieren tabel.

Wat nu nog mist​

Eén node uitwerken lukt. Welke node de volgende is, dat is bouwsteen 4.

Door naar bouwsteen 4: kies de volgende →.