Algoritme van Dijkstra
Je routeplanner kent de snelste weg van je voordeur naar bijna overal. In de kern van dat idee zit een algoritme dat Edsger Dijkstra in 1956 in zo'n twintig minuten bedacht: groei vanaf de start naar buiten en maak altijd eerst de dichtstbijzijnde plek af.
Het idee
Stel je steden voor die verbonden zijn door wegen van verschillende lengte. De vraag is: wat is de kortste weg van mijn stad naar elke andere? Breedte-eerst zoeken beantwoordt die vraag als elke weg even zwaar telt, maar hier kan een route met meer wegen korter zijn. Het algoritme van Dijkstra houdt voor elke stad de kortste afstand tot nu toe bij en laat een gebied groeien van steden waarvan de afstand zeker is, door steeds de dichtstbijzijnde stad toe te voegen die nog niet zeker is.
Stap voor stap
Geef de start afstand 0 en elke andere knoop oneindig. Zet de start in een prioriteitswachtrij, een wachtrij die altijd de knoop met de kleinste afstand teruggeeft. Neem die knoop; de afstand is nu definitief. Bereken voor elke buur die nog niet definitief is de afstand via deze knoop: de afstand van de knoop plus de lengte van de kant. Is dat korter dan de afstand van de buur tot nu toe, verlaag die dan, onthoud deze knoop als de weg erheen en zet de buur in de wachtrij. Dit heet het relaxeren van een kant. Herhaal tot de wachtrij leeg is, of tot het doel eruit wordt genomen.
Een voorbeeld
Neem de kanten A–B met lengte 4, A–C 1, B–C 2, B–D 1, C–D 5 en D–E 3, en begin bij A. A nemen geeft B afstand 4 en C afstand 1. C ligt het dichtst, dus die is definitief op 1; via C daalt B naar 1 + 2 = 3 en krijgt D 1 + 5 = 6. Nu ligt B het dichtst, definitief op 3, en via B daalt D naar 3 + 1 = 4. D is definitief op 4 en geeft E 4 + 3 = 7. De kortste weg van A naar E is dus A → C → B → D → E, lengte 7, ook al gebruikt A → B → D → E minder kanten en heeft die lengte 8.
Waarom het klopt
Stel dat knoop X de dichtstbijzijnde in de wachtrij is, op afstand d. Elke andere weg van de start naar X moet het gebied van definitieve knopen ergens verlaten, en de eerste knoop die hij buiten dat gebied bereikt, zit in de wachtrij en ligt dus al minstens d ver weg. De rest van de weg kan hem niet korter maken, want geen kant is negatief. Dus is d de kortste afstand tot X. Met een negatieve kant gaat die redenering niet op; dan gebruik je het algoritme van Bellman–Ford, dat elke kant steeds opnieuw relaxeert.
Geschiedenis en toepassingen
Edsger W. Dijkstra bedacht het algoritme in 1956 om een nieuwe computer, de ARMAC in Amsterdam, te demonstreren door routes tussen Nederlandse steden te vinden, en publiceerde het in 1959. Hetzelfde idee, met een slimmere wachtrij, draait in routeplanners en in routeringsprotocollen van het internet zoals OSPF en IS-IS, die de kortste weg voor data tussen routers bepalen. A*-zoeken voegt een schatting toe van de afstand die nog te gaan is, zodat het op het doel af kan gaan en minder knopen bekijkt.
Probeer het zelf
Open de app en druk op Stap. De getallen op de kanten zijn hun lengtes, en het getal op elke knoop is de afstand tot nu toe. Knopen in de wachtrij zijn blauw, definitieve knopen groen, en de wachtrij onder de graaf toont ze met hun afstanden, dichtstbijzijnde eerst. Let op de momenten waarop een afstand daalt omdat een route die langer lijkt toch korter blijkt, en kies een doel om het zoeken te zien stoppen zodra het doel definitief is.
Veelgestelde vragen
Wat is de tijdcomplexiteit van het algoritme van Dijkstra?
Dat hangt af van de prioriteitswachtrij. Met een eenvoudige lijst is het O(V²) voor V knopen; met een binaire heap O((V + E) log V) voor E kanten; met een Fibonacci-heap O(E + V log V), zoals Michael Fredman en Robert Tarjan in 1984 lieten zien.
Kan het algoritme van Dijkstra omgaan met negatieve gewichten?
Nee. Het gaat ervan uit dat de afstand van een knoop niet meer kan verbeteren zodra die knoop de dichtstbijzijnde in de wachtrij is, en een negatieve kant kan dat doorbreken. Gebruik het algoritme van Bellman–Ford voor grafen met negatieve kanten.
Vindt het algoritme van Dijkstra het pad naar elke knoop?
Ja. Als je het tot het einde laat lopen, geeft het de kortste afstand van de start naar elke bereikbare knoop, en de onthouden knopen vormen een boom van kortste paden. Vroeg stoppen zodra het doel definitief is, scheelt werk als je maar één pad nodig hebt.
Hoe hangt het algoritme van Dijkstra samen met A*?
A*-zoeken is het algoritme van Dijkstra met een hint: het ordent de wachtrij op de afstand tot nu toe plus een schatting van de afstand die nog te gaan is, zoals de afstand in rechte lijn op een kaart. Met een goede schatting vindt het hetzelfde kortste pad en bekijkt het veel minder knopen.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Probeer het algoritme van Dijkstra