8.11 Pas aan — reconstrueer het pad

Leerdoel: je breidt Dijkstra uit zodat hij niet alleen de afstand teruggeeft, maar ook welk pad dat is — bijv. A → B → D.

Wat we willen

Tot nu toe weten we: "D is 5 minuten van A." Maar welke route? Via B of via C?

Antwoord moet zijn: ['A', 'B', 'D'] — de stappen op de kortste route.

Het idee — voorgangers bijhouden

Op het moment dat we tijdens de relax-stap de afstand voor een buur verbeteren, onthouden we vanaf welke node die verbetering kwam. Die node noemen we de voorganger.

voorgangers = {}
...
if nieuwe < afstanden[buur]:
    afstanden[buur] = nieuwe
    voorgangers[buur] = huidige     # ← nieuwe regel

Voor onze mini-graph, met start A, krijg je aan het eind:

voorgangers = {'B': 'A', 'C': 'A', 'D': 'B'}

Lees: "voorganger van B is A, voorganger van C is A, voorganger van D is B."

Het pad terugvinden

Om het pad van A naar D te krijgen, beginnen we bij D en lopen de voorgangers terug:

• D → voorgangers['D'] = 'B'
• B → voorgangers['B'] = 'A'
• A is de start → klaar.

Verzameld: [D, B, A]. Draai om: [A, B, D]. Dat is het pad.

Opdracht

Pas dijkstra aan om voorgangers mee te houden. Schrijf een hulpfunctie reconstrueer_pad die het pad teruggeeft.

Python

Code-omgeving wordt voorbereid…

Tip

Voor dijkstra: één regel onder de afstand-update.

voorgangers[buur] = huidige

Voor reconstrueer_pad: een while-lus die zolang huidige niet None is, hem toevoegt en dan naar voorgangers.get(huidige) springt. Aan het eind: pad.reverse() of pad[::-1].

Antwoord

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

    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
                voorgangers[buur] = huidige

    return afstanden, voorgangers


def reconstrueer_pad(voorgangers, start, doel):
    pad = []
    huidige = doel
    while huidige is not None:
        pad.append(huidige)
        if huidige == start:
            break
        huidige = voorgangers.get(huidige)
    pad.reverse()
    return pad if pad and pad[0] == start else []

Verwacht:

Afstanden:   {'A': 0, 'B': 4, 'C': 2, 'D': 5}
Voorgangers: {'B': 'A', 'C': 'A', 'D': 'B'}
Pad A→D:     ['A', 'B', 'D']

voorgangers.get(huidige) returnt None als de node niet in de dict zit — dat is hoe we ontdekken dat we klaar zijn met terug-lopen.

De extra check pad[0] == start vangt het geval af dat doel onbereikbaar is.

Visualiseer het pad

Python

Code-omgeving wordt voorbereid…

Wat zie je?

Het pad A → B → D is rood met dikkere lijnen. De edge A → C → D blijft grijs — die route bestaat wel, maar is langer (10 > 5).

Niet altijd intuïtief: B ligt "verder weg" qua nummer (4 vs 2), maar heeft een zeer korte stap naar D (gewicht 1). Daardoor wint de B-route.

Door naar stap 12: bouw zelf →.