Er gaat iets mis — top-3 fouten

Leerdoel: je herkent de drie fouten die iedereen bij Dijkstra een keer maakt.

Edge maar één kant op zetten

Geen foutmelding, wel een fout antwoord: sommige nodes blijven op inf staan terwijl ze bereikbaar zijn.

Oorzaak: in een graph waar je elke weg beide kanten op mag, staat elke verbinding twee keer in de dict. Mis je er één, dan bestaat die kant voor het algoritme niet.

# FOUT — A → B staat alleen onder A
graph = {
    'A': [('B', 4)],
    'B': [],            # ← B kan niet terug naar A
}

# GOED
graph = {
    'A': [('B', 4)],
    'B': [('A', 4)],
}

Tip: bouw de dict op uit een lijst van edges, dan kun je geen kant vergeten:

edges = [('A', 'B', 4), ('A', 'C', 2), ('B', 'D', 1), ('C', 'D', 8)]
graph = {}
for u, v, w in edges:
    if u not in graph:
        graph[u] = []
    if v not in graph:
        graph[v] = []
    graph[u].append((v, w))
    graph[v].append((u, w))

bezocht.add() vergeten — oneindige lus

Geen foutmelding, Python loopt door zonder einde. De browser-tab bevriest, en de Reset-knop reageert dan ook niet meer, want Python draait in dezelfde tab als de les. Sluit de tab en open de les opnieuw. Je code ben je dan kwijt, dus kopieer hem eerst naar een kladblok als je iets uitprobeert wat mis kan gaan.

Oorzaak: zonder bezocht.add(huidige) blijf je dezelfde node steeds opnieuw kiezen. De hoofdlus eindigt nooit.

while True:
    huidige = kies_volgende(afstanden, bezocht)
    if huidige is None:
        break
    # bezocht.add(huidige) ← VERGETEN!
    for buur, gewicht in graph[huidige]:
        ...

Oplossing: markeer de node zodra je hem gekozen hebt, vóór je opnieuw kiest:

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

Of de regel vóór of ná de relax-lus staat maakt niet uit — die lus kijkt niet naar bezocht. Dat hij er staat wel.

Negatieve gewichten gebruiken

Geen foutmelding, wel een antwoord dat stilletjes niet klopt.

Oorzaak: Dijkstra gaat ervan uit dat een node die "klaar" is zijn afstand niet meer kan verbeteren. Een negatieve edge kan dat omgooien: een node die al klaar was wordt alsnog korter, maar zijn buren zijn al uitgerekend met de oude afstand.

Dit voorbeeld heeft eenrichtingswegen: elke edge staat maar aan één kant in de dict. Dat moet wel, want een negatieve weg die je ook terug mag nemen is een rondje dat elke keer goedkoper wordt, en dan bestaat er geen kortste route.

Python

Code-omgeving wordt voorbereid…

Wat zie je?

{'A': 0, 'B': -1, 'C': 3, 'D': 2}

D hoort 0 te zijn: A → C → B → D is 3 − 4 + 1 = 0. Dijkstra zegt 2. Wat er gebeurde: B werd klaar verklaard op afstand 1 en D kreeg 1 + 1 = 2. Pas daarna kwam C aan de beurt en zakte B naar −1, maar B was al klaar, dus niemand rekende D opnieuw uit.

Oplossing: voor negatieve gewichten gebruik je Bellman-Ford, een ander algoritme. Routekaarten, vluchtprijzen en netwerkvertragingen hebben alleen positieve gewichten, en daar is Dijkstra voor.

Door naar cheatsheet →.