Je eerste antwoord klopt niet. Het gaat niet om de kortste afstand naar naar een buur van elk punt, maar om de kortste afstand van elk punt naar punt A.
Het algoritme van Dijkstra vind je hier:
https://nl.wikipedia.org/wiki/Kortstepad-algoritme
We zoeken dus de kortste verbinding van elk punt naar punt A (= gb = beginpunt = startpunt).
We beginnen (= "initieel geldt" op die wiki pagina):
A = {A} verzameling A bestaat uit punt A
X = {F, E, G, B} deze punten zijn direct verbonden met punt A
d(A) = 0
voor alle punten g in X geldt: d(g) = gewicht(gb, g), dus:
- d(F) = gewicht(A, F) = 2, vanaf punt A
- d(E) = gewicht(A, E) = 20, vanaf punt A
- d(G) = gewicht(A, G) = 4, vanaf punt A
- d(B) = gewicht(A, B) = 8, vanaf punt A
Voor alle andere punten geldt: d(g) = oneindig = oo, dus:
- d(H) = oo
- d(C) = oo
- d(D) = oo
Nu gaan we de volgende lus steeds herhalen, totdat we alle afstanden gevonden hebben:
1. Kies uit X het punt x met minimale waarde d(x). Bij ons is dat punt F met waarde d(F) = 2
Deze waarde is definitief. We weten nu dus:
d(A) = 0
d(F) = 2 (vanuit punt A)
Verplaats x naar verzameling A:
A = { A, F }
2. Voor alle punten z bereikbaar vanuit x (= punt F), en die nog niet in verzameling A zitten doen we het volgende: ...
de punten bereikbaar vanuit F zijn punt A en punt E, alleen punt E zit nog niet in verzameling A, dus voor punt E:
2.1 zit E nog niet in X: niet waar want E zit wel in X, dus doen we bij 2.1 niets
2.2 zit E wel in X: klopt, dus vergelijken we:
- de huidige d(E) = 20, met:
- d(F) + gew(F, E) = 2 + 14 = 16
De laatste is kleiner, dus nu wordt
d(E) = 16, vanaf punt F
Onze eerste lus is nu klaar, en we hebben nu deze situatie:
A = { A, F }
X = { E, G, B }
d(A) = 0
d(F) = 2, pad komt vanaf punt A
d(E) = 16, pad komt vanaf punt F
d(G) = 4, vanaf punt A
d(B) = 8, vanaf punt A
d(H) = oo
d(C) = oo
d(D) = oo
Hier in een plaatje, in rood de definitieve verbinding, in blauw de mogelijke verbindingen.
Kan je nu zelf de lus nog een keer uitvoeren?
En nog een keer en nog een keer ... totdat alle punten hun definitieve afstand tot punt A hebben?
Je tweede opdracht volgt hetzelfde schema, maar nu vanuit een matrix = tabel M.
Als je het gemakkelijker vindt, kan je M ook eerst tekenen als een graaf zoals in de eerste opdracht.