Pas aan — reconstrueer het pad

Leerdoel: je breidt Dijkstra uit zodat hij niet alleen de afstand teruggeeft, maar ook het pad, zoals A → B → D.

Wat we willen

Tot nu toe weten we dat D 5 minuten van A ligt, maar niet waarlangs: via B of via C? Het antwoord moet ['A', 'B', 'D'] worden, de stappen van de kortste route.

Het idee — voorgangers bijhouden

Op het moment dat de relax-stap de afstand van een buur verbetert, onthouden we vanaf welke node die verbetering kwam. Die node is 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'}

De voorganger van B is A, die van C ook, en die van D is B.

Het pad terugvinden

Het pad van A naar D vind je door bij D te beginnen en de voorgangers terug te lopen: voorgangers['D'] is B, voorgangers['B'] is A, en A is de start. Dat geeft [D, B, A]; omgedraaid is het pad [A, B, D].

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 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 = {}
    for node in graph:
        afstanden[node] = float('inf')
    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()
    if pad and pad[0] == start:
        return pad
    return []


graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('D', 1)],
    'C': [('A', 2), ('D', 8)],
    'D': [('B', 1), ('C', 8)],
}

afstanden, voorgangers = dijkstra(graph, 'A')
pad = reconstrueer_pad(voorgangers, 'A', 'D')
print("Afstanden:  ", afstanden)
print("Voorgangers:", voorgangers)
print("Pad A→D:    ", pad)

assert voorgangers == {'B': 'A', 'C': 'A', 'D': 'B'}, f"voorgangers hoort {{'B': 'A', 'C': 'A', 'D': 'B'}} te zijn, is {voorgangers}"
assert pad == ['A', 'B', 'D'], f"het pad hoort ['A', 'B', 'D'] te zijn, is {pad}"
print("Alle tests geslaagd.")

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

voorgangers.get(huidige) geeft None als de node niet in de dict zit; zo merk je dat het teruglopen klaar is. De check pad[0] == start vangt het geval dat doel onbereikbaar is.

Visualiseer het pad

Python

Code-omgeving wordt voorbereid…

Wat zie je?

Het pad A → B → D is rood en dikker. De route A → C → D blijft grijs: die bestaat wel, maar is langer (10 tegenover 5).

Niet altijd intuïtief: B ligt verder van A dan C (4 tegenover 2), maar heeft een korte stap naar D (gewicht 1). Daardoor wint de B-route.

Door naar bouw zelf →.