Nederlands
Menu

Wat is Algoritme van Dijkstra?

Algoritme dat de kortste paden vindt van één startknoop naar elke knoop in een graaf waarvan de gewichten van de kanten 0 of groter zijn. Het legt herhaaldelijk de dichtstbijzijnde knoop vast waarvan de afstand nog niet definitief is, en werkt de afstanden van haar buren bij. Met negatieve gewichten werkt het niet correct.

Japanse benaming: ダイクストラ法

“Algoritme van Dijkstra” komt voor in 3 oefenvragen uit 1 onderwerpen, bijv. Datastructuren en algoritmen.

Vakgebied: Datastructuren en algoritmen

Werkwijze

Zet de afstand van de startknoop op 0 en die van alle andere knopen op oneindig, en markeer elke knoop als niet definitief. Kies de niet-definitieve knoop met de kleinste afstand, leg die vast, en werk voor elke kant die eruit vertrekt de afstand van de knoop aan het andere eind bij als „vastgelegde afstand + gewicht van de kant” kleiner is dan haar huidige afstand (relaxatie). Herhaal dit tot elke knoop definitief is. Wie bij elke bijwerking de vorige knoop vastlegt, kan het kortste pad zelf achteraf terugvolgen.

Complexiteit en prioriteitswachtrijen

Elke keer alle knopen doorzoeken naar het minimum kost O(V²) voor V knopen. Met een prioriteitswachtrij op basis van een binaire heap daalt dit tot O((V + E) log V), waarbij E het aantal kanten is; dat is veel sneller voor ijle grafen zoals wegennetten. De graaf wordt meestal als adjacentielijsten opgeslagen. Navigatiesystemen in auto's combineren het algoritme met A*-zoeken, dat een schatting van de resterende afstand toevoegt om de zoekactie naar de bestemming te sturen, en met versnellingstechnieken die vooraf berekende informatie gebruiken.

Negatieve gewichten en andere algoritmen

Het algoritme van Dijkstra legt knopen vast in de veronderstelling dat een omweg via andere knopen een afstand alleen kan vergroten en nooit verkleinen. Met negatieve kanten kan een vastgelegde afstand later korter worden, dus juiste antwoorden zijn niet gegarandeerd. Bij negatieve gewichten wordt het algoritme van Bellman-Ford gebruikt, dat elke kant V−1 keer relaxeert; het kan ook negatieve cykels detecteren. Voor kortste paden tussen alle paren knopen wordt ook het algoritme van Floyd-Warshall (O(V³)) gebruikt, dat op dynamisch programmeren is gebaseerd. Bij routering in netwerken gebruiken linkstateprotocollen zoals OSPF het algoritme van Dijkstra in elke router om routes te berekenen.

Nu oefenen: vragen over Algoritme van Dijkstra

In een ongerichte graaf zijn de gewichten (afstanden) van de kanten S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 en A−T: 6. Welk kortste pad van S naar T vindt het algoritme van Dijkstra, en wat is de lengte ervan?

  1. AS→A→C→T, lengte 8
  2. BS→B→A→C→T, lengte 7
  3. CS→B→C→T, lengte 9
Antwoord en toelichting tonen

Antwoord: B. S→B→A→C→T, lengte 7

Het algoritme van Dijkstra legt herhaaldelijk de dichtstbijzijnde knoop vast waarvan de afstand nog niet definitief is, en werkt de afstanden van haar buren bij. Vanuit S (0) wordt B vastgelegd op 1, en via B krijgt A de afstand 1 + 2 = 3, korter dan de directe 4. Na het vastleggen van A (3) krijgt C de waarde 3 + 1 = 4 en T de waarde 3 + 6 = 9, en na het vastleggen van C (4) wordt T bijgewerkt tot 4 + 3 = 7. Het kortste pad is dus S→B→A→C→T met lengte 7. S→A→C→T (8) is langer omdat het S−A rechtstreeks neemt, en S→B→C→T (9) is langer omdat B−C het grote gewicht 5 heeft.

Aan welke voorwaarde moet de graaf voldoen opdat het algoritme van Dijkstra juiste kortste paden vindt?

  1. ADe graaf heeft geen cykels (paden die naar dezelfde knoop terugkeren)
  2. BDe kanten hebben geen richting
  3. CAlle gewichten van de kanten zijn 0 of groter
Antwoord en toelichting tonen

Antwoord: C. Alle gewichten van de kanten zijn 0 of groter

Het algoritme van Dijkstra legt de nog niet vastgelegde knoop met de kleinste afstand vast. Dat berust op de aanname dat een omweg via andere knopen een afstand alleen kan vergroten en nooit verkleinen. Met een kant met negatief gewicht kan een afstand later via een andere route korter worden: in een gerichte graaf met S→A 2, S→B 3 en B→A −2 wordt A vastgelegd op 2, voordat het pad S→B→A met lengte 1 wordt gevonden. Bij negatieve gewichten worden methoden zoals het algoritme van Bellman-Ford gebruikt. Het algoritme van Dijkstra werkt ook met cykels en met gerichte kanten, zolang alle gewichten 0 of groter zijn.

Veelgestelde vragen

Hoe hangt het algoritme van Dijkstra samen met breedte-eerst zoeken?

Als elke kant gewicht 1 heeft, legt het algoritme van Dijkstra de knopen vast in dezelfde volgorde als breedte-eerst zoeken. Het kan worden gezien als een veralgemening voor verschillende gewichten, waarbij de wachtrij wordt vervangen door een prioriteitswachtrij die de kleinste afstand als eerste teruggeeft.

Kan het algoritme van Dijkstra worden gebruikt op gerichte grafen?

Ja. Zolang de gewichten 0 of groter zijn, vindt het correcte kortste paden in gerichte en ongerichte grafen, ook in grafen met cykels.

“Algoritme van Dijkstra” in de toelichting

Vragen met “Algoritme van Dijkstra” (3)

  1. In een ongerichte graaf zijn de gewichten (afstanden) van de kanten S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 en A−T: 6. Welk kortste pad van S naar T vindt het algoritme van Dijkstra, en wat is de lengte ervan?
  2. Aan welke voorwaarde moet de graaf voldoen opdat het algoritme van Dijkstra juiste kortste paden vindt?
  3. Wat is een geschikte manier om een ijle graaf, een graaf met weinig kanten in verhouding tot het aantal knopen, in het geheugen op te slaan, zoals een wegennet met ongeveer 1 miljoen knopen en 3 miljoen kanten?

Verwante termen

Breedte-eerst zoeken (breadth-first search) Binair zoeken (binary search) Binaire heap (binary heap) Binaire zoekboom (binary search tree) Diepte-eerst zoeken (depth-first search) Dynamisch programmeren (dynamic programming) Gelinkte lijst (linked list) Gretig algoritme (greedy algorithm) Hashtabel (hash table) Recursie

Naar de woordenlijst