8.10 Het complete algoritme

Leerdoel: je ziet alle bouwstenen in één functie samenkomen en visualiseert het eindresultaat op de graph.

Alles samen

def kies_volgende(afstanden, bezocht):
    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
    return beste_node


def dijkstra(graph, start):
    afstanden = {node: float('inf') for node in graph}
    afstanden[start] = 0
    bezocht = set()

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

    return afstanden

Zie je de bouwstenen?

• Regels 1-9 → bouwsteen 4: kies volgende node.
• Regel 13 → bouwsteen 2: afstanden initialiseren.
• Regel 14 → start op 0 zetten.
• Regel 15 → bezocht-set leeg.
• Regels 17-25 → bouwsteen 6: de lus om bouwsteen 5 (één ronde).
• Regels 22-25 → bouwsteen 3: relax buren.

Voorspel

We runnen dijkstra(graph, 'A') op de mini-graph. Wat denk je dat er als resultaat uit komt?

Antwoord

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

Exact wat je op papier en in de losse rondes ook kreeg.

Run

Python

Code-omgeving wordt voorbereid…

Visualiseer de afstanden

Onze graph met op elke node zijn kortste afstand vanaf A:

Python

Code-omgeving wordt voorbereid…

Wat zie je?

Elke node toont zijn kortste afstand vanaf A (groen = startnode):

• A: 0
• B: 4 (direct)
• C: 2 (direct)
• D: 5 (via B, niet via C!)

Onderzoek

Speel met de code. Probeer:

1. Een andere startnode: dijkstra(graph, 'D').
2. Maak A → B veel duurder (bv. gewicht 100). Hoe verandert de afstand naar B?
3. Voeg een extra node E toe met een verbinding naar B. Welk gewicht moet hij hebben om binnen 6 te vallen?

Python

Code-omgeving wordt voorbereid…

Door naar stap 11: pad reconstrueren →.