Page 2 - Grafentheorie Hoofdstuk 7 Kortste route

HS 7: Kortste route

7 Kortste route

7.1 Inleiding

Met een navigatiesysteem (GPS) kan je de kortste route van jouw huidige positie naar de bestemming
berekenen. Meestal betekent “kortste" dat dit de weg is met het kleinste aantal kilometer. Afhankelijk
van de instellingen of voorkeuren, kan "kortste" ook betekenen dat de voorgestelde weg het minste tijd
vraagt, of het minste kost aan tolgeld, en daarmee zijn de mogelijkheden niet op.

Een eenvoudig voorbeeld
Gegeven zijn een aantal steden, voorgesteld door de knopen A tot en met E.

De steden zijn verbonden met een aantal spoorlijnen waarbij de getallen de afstanden voorstellen om
van de ene naar de andere stad te reizen.

Bepaal de kortste route om van stad A naar stad E te reizen.
Wij onderzoeken nu een aantal algoritmen om dit probleem op te lossen.

7.2 “Brute force” algoritme

Een werkwijze om dit probleem op te lossen is alle mogelijke paden (zonder cykels) van A tot E noteren,
voor elk pad de afstand te bepalen en tenslotte het pad met de kortste afstand te kiezen.
Omdat het aantal steden en verbindingen klein is zijn de mogelijkheden beperkt.
ADCE 40 + 60 + 80 =180
t
ABDCE 80 + 30 + 60 + 80 =250 e
n
ADBCE 40 + 30 + 20 + 80 = 170 . o
l
ABCE 80 + 20 + 80 =180 e
h
…. t
a
m
.
Dit algoritme is geenszins een “slim” en efficiënt algoritme omdat voor een groot aantal steden deze w
werkwijze praktisch onhaalbaar is. w
w

© 2021 Ivan De Winne ivan@mathelo.net 1