Page 4 - Grafentheorie Hoofdstuk 7 Kortste route

HS 7: Kortste route

Voorbeeld 1
Een fietskoerier moet een pizza aan huis leveren. Dit moet uiteraard zo snel mogelijk gebeuren.
De situatie wordt hieronder schematisch weergegeven met een graaf. De fietskoerier vertrekt vanuit de
pizzazaak S en moet de pizza afleveren in E. De knopen stellen de kruispunten voor en de bogen geven
de afstanden weer.

1. Geef de startknoop S het permanente label 0.

2. Bekijk alle buren van de startknoop S. De buren van S zijn A, B, C en D.
Deze buren krijgen een tijdelijk label, zijnde de afstand tot de startknoop S.

t
e
3. Kies van deze tijdelijke labels de knoop met het kleinste label. In dit geval de knoop B. n
.
Maak dit label permanent en voeg de boog SB toe aan het pad. o
l
e
h
t
a
m
.
w
w
w

© 2021 Ivan De Winne ivan@mathelo.net 3