Het complete algoritme

Leerdoel: je ziet alle bouwstenen samenkomen in één functie, en je tekent het resultaat 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 = {}
    for node in graph:
        afstanden[node] = float('inf')
    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

1. Regel 1-10:

   Bouwsteen 4 — de helper kies_volgende: van alle onbezochte knopen die met de laagste afstand tot nu toe. Zijn ze allemaal bezocht, dan blijft beste_node op None staan.

2. Regel 13:

   Bouwsteen 1 komt binnen als graph: de dict met per knoop zijn buren.

3. Regel 14-16:

   Bouwsteen 2, stap 0 — elke knoop begint op oneindig: nog geen route bekend.

4. Regel 17:

   Behalve het startpunt: daar sta je al, afstand 0.

5. Regel 18:

   De lege set voor knopen die definitief af zijn.

6. Regel 20-23:

   Bouwsteen 6 — de hoofdlus: kies de volgende knoop, en stop zodra er geen onbezochte meer over is.

7. Regel 24:

   Bouwsteen 5 — markeer de gekozen knoop als af, vóór de volgende ronde kiest.

8. Regel 25-28:

   Bouwsteen 3 — relax de buren: is de route via huidige korter dan wat we voor de buur hadden, dan overschrijven we die afstand.

Voorspel

We draaien dijkstra(graph, 'A') op de kleine graph. Wat komt eruit?

Antwoord

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

Wat je op papier en in de losse rondes ook kreeg.

Run

Python

Code-omgeving wordt voorbereid…

Visualiseer de afstanden

De 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; de startnode is groen. B en C liggen direct aan A, op 4 en 2. D staat op 5, via B en niet via C.

Onderzoek

kies_volgende en dijkstra van hierboven staan al klaar; in het veld staat alleen de graph. Pas hem aan:

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 mag die edge hoogstens hebben als E op afstand 6 of minder moet liggen?

Python

Code-omgeving wordt voorbereid…

Wat zie je?

1. {'A': 5, 'B': 1, 'C': 7, 'D': 0}. C ligt nu op 7, via B en A (1 + 4 + 2), en niet op 8 via de directe edge.
2. B komt op 11 te staan, via C en D (2 + 8 + 1). D wordt 10: via B kost hij nu 101.
3. Hoogstens 2: B ligt op 4, dus E op 4 plus het gewicht. Zet de edge in beide lijsten, ('E', 2) bij B en 'E': [('B', 2)]. Staat hij alleen bij E, dan komt Dijkstra vanaf A nooit bij E en blijft de afstand inf.

Door naar pad reconstrueren →.