Page 5 - Grafentheorie Hoofdstuk 7 Kortste route

P. 5

HS 7: Kortste route

4. Kijk nu naar de buren van B. De buren van B (die nog geen permanent label hebben) zijn A en C.
Geef deze buren nieuwe tijdelijke labels.
Indien de buur al een label heeft dan wordt het nieuwe tijdelijke label het minimum van de som
van het label van B en het oude tijdelijke label.
Het tijdelijke label van A wordt 4 + 1 = 5 (is kleiner dan 7)
Het tijdelijke label van C wordt 4 + 3 = 7 (is kleiner dan 9)
De knoop met het kleinste label is hier A. Het label van A wordt permanent.
Voeg ook de boog BA toe aan het pad.

5. De knoop met het kleinste label is nu A. Bekijk de buren van A. De enige buur van A is E.
Het tijdelijk label van E wordt 5 + 6 = 11.

6. Kies opnieuw de knoop met het kleinste label. In dit geval zijn er twee mogelijkheden C of D.
Vanuit C wordt het tijdelijke label van E gelijk aan 7 + 3 = 10.
Vanuit D zou dit tijdelijke label van E gelijk worden aan 7 + 4 = 11
Daarom kiezen wij C dat als permanent label 7 krijgt en wij passen ook de bogen aan.
Ook het punt E krijgt nu een permanent label omdat er geen korter pad kan gevonden worden.

t
e
n
.
o
l
e
h
t
a

m
Besluit het kortste pad is SBCE met als lengte 4 + 3 + 3. .
w
Je kan nagaan dat alle andere mogelijkheden om vanuit S naar E te gaan langer zijn. w
Uitgewerkt GeoGebra bestand opgave link https://www.geogebra.org/m/d2fwn4jk w
Oplossing: https://www.geogebra.org/m/g7jckbgc

1 2 3 4 5 6 7 8 9 10