Page 3 - Grafentheorie Hoofdstuk 7 Kortste route

HS 7: Kortste route

7.3 Dichtste-buur algoritme

Ook bij dit probleem kan men dit algoritme proberen toe te passen.

Hierbij ga je vanuit de startknoop A simpelweg naar de dichtstbijzijnde knoop.

Deze werkwijze levert niet altijd de kortste route zoals blijkt ook onderstaand eenvoudig
(tegen)voorbeeld.

7.4 Algoritme van Dijkstra

Een efficiënt algoritme waarmee men het kortste pad vindt is het algoritme van de Nederlandse
wiskundige Edsger Dijkstra.

Dijkstra bedacht dit eenvoudig algoritme in 1959 zonder pen of papier op een zonnig terras terwijl hij
met zijn vrouw een kopje koffie dronk.

Met dit algoritme kan men stap voor stap de kortste route bepalen tussen 2 knopen van een
(samenhangende) graaf. Dit algoritme vergelijkt niet alle mogelijke routes met elkaar maar berekent
stap voor stap de kortst mogelijke afstand.

Het idee van dit algoritme is dat wij de knopen voorzien van een
label en telkens de knoop met het kleinste label kiezen. t
e
Wij maken hierbij onderscheid tussen: n
.
o
• Tijdelijke labels: geven de kortste afstand weer van de l
startknoop tot die bepaalde knoop die we tot dan toe e
h
gevonden hebben. t
a
Bij iedere stap die we doen kan dit tijdelijke label kleiner worden. m
.
• Permanente labels: indien wij vaststellen dat er geen w
korter pad bestaat tot een bepaalde knoop dan wordt w
het tijdelijke label omgezet naar een permanent label.
w

© 2021 Ivan De Winne ivan@mathelo.net 2