Ga naar hoofdinhoud

8.6 Bouwsteen 3 — update één buur (relax)

Leerdoel: je vertaalt stap B uit de pen-en-papier-aanpak naar Python: één buur bekijken en zijn afstand updaten als de route via mij korter is.

Wat we willen​

Op papier deed je dit voor elke buur:

"Kijk: vanuit mij + de stap naar buur, geeft dat een kortere afstand dan wat buur nu heeft? Zo ja, update."

In ons mini-graph-voorbeeld, ronde 3: vanuit B (afstand 4) keken we naar buur D (gewicht 1). Kandidaat = 4 + 1 = 5. D had 10 → update naar 5.

De formule​

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

Drie regels. Eén berekening, één vergelijking, één toewijzing.

  • afstanden[huidige] = afstand vanuit start naar de node waar we nu staan.
  • gewicht = de kost om naar deze buur te lopen.
  • nieuwe_afstand = totaal als we via mij gaan.

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?​

Run hetzelfde, maar nu kijken we vanuit C (afstand 2) naar buur A (gewicht 2). Kandidaat = 2 + 2 = 4. Maar A heeft al 0. Dus geen update.

Python
Code-omgeving wordt voorbereid…

Voor alle buren van een node​

Dit is wat we straks per ronde willen doen. Eé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) updaten we tegelijk B en C in één lusje.

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}

Dit komt precies overeen met ronde 1 uit je pen-en-papier-tabel.

Wat nu nog mist​

We kunnen één node uitwerken. Maar welke node nemen we als volgende? Dat is bouwsteen 4: kiezen wie aan de beurt is.

Door naar bouwsteen 4: kies de volgende →.