Toepassen van Dijkstra

Dijkstra

Het algoritme begrijpen

Het algoritme werkt door iteratief het knooppunt te selecteren met de kleinste voorlopige afstand, dan de afstanden naar de naburige knooppunten bij te werken. Het gaat door tot het kortste pad naar de doelknooppunt is gevonden of alle knooppunten zijn verwerkt.

Stapsgewijze berekening

Stel dat we een grafiek hebben met de knooppunten A, B, C, D en E, en de volgende gewogen randen:

• A tot B: 4
• A tot C: 2
• B tot C: 1
• B tot D: 5
• C tot D: 8
• C tot E: 10
• D tot en met E: 2

Beginnend vanaf knooppunt A, initialiseer afstanden: A = 0, anderen = oneindigheid. Markeer alle knooppunten als niet bezocht.

Iteratie 1

Knooppunt A (afstand 0) bijwerken van de naburige knooppunten B en C:

Afstand tot B: 4 (A + 4) tot C: 2 (A + 2). Mark A zoals bezocht.

iteratie 2

Selecteer knooppunt C (afstand 2). Update buren D en E:

Afstand tot D: 10 (C + 8) tot E: 12 (C + 10). Mark C zoals bezocht.

iteratie 3

Selecteer knooppunt B (afstand 4). Update buurman D:

Afstand tot D: 9 (B + 5), wat minder is dan vorige 10. Update D's afstand tot 9. Mark B zoals bezocht.

iteratie 4

Selecteer node D (afstand 9). Update buurman E:

Afstand tot E: 11 (D + 2). Update E's afstand tot 11. Mark D zoals bezocht.

Iteratie 5

Het resterende knooppunt E heeft een afstand van 11. Mark E zoals bezocht. Het kortste pad van A naar E is door de knopen C, B, D en E met totale afstand 11.