- Huidig
- In de wachtrij
- Definitief
- Pad
Algoritme van Dijkstra
Het algoritme van Dijkstra vindt de kortste route van een start naar elke andere knoop als de kanten een lengte hebben, zoals wegen tussen steden. Het groeit vanaf de start naar buiten en neemt altijd de dichtstbijzijnde knoop die nog niet klaar is. Klik op een knoop om daar te beginnen, kies eventueel een doel, en ga stap voor stap om de wachtrij te zien, elke afstand te zien dalen als er kortere wegen opduiken, en het kortste pad te zien verschijnen. Druk op Afspelen om het zoeken te volgen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om ergens heen te springen. Klik op een knoop om die de start te maken; zet de klik op Doel en klik op een andere knoop om een kortste pad ernaartoe te zoeken. Het getal op elke kant is de lengte ervan, het getal op elke knoop de kortste afstand tot nu toe, en de rij onder de graaf is de wachtrij, dichtstbijzijnde eerst. Nieuwe graaf maakt een andere graaf; kies hoeveel knopen en kanten die heeft. Als het bord geselecteerd is, gaan de pijltjestoetsen een stap verder of terug, start en pauzeert de spatiebalk, en springen Home en End naar het begin en het einde.
Hoe het werkt
- Klik op een knoop om die de start te maken. Wil je een pad zoeken, zet de klik dan op Doel en klik op een andere knoop.
- Druk op Afspelen, of gebruik Stap en Terug om stap voor stap te gaan. Sleep de stappenschuif om naar elk punt in het zoeken te springen.
- Volg de wachtrij onder de graaf en de afstand op elke knoop. Nieuwe graaf maakt een andere graaf om te proberen.
Hoe het algoritme van Dijkstra werkt
Geef de start afstand 0 en elke andere knoop oneindig, en zet de start in een wachtrij. Herhaal dan: neem de knoop in de wachtrij met de kleinste afstand en maak die afstand definitief. Tel voor elke buur die nog niet definitief is de lengte van de kant op bij de afstand van de knoop. Is de som korter dan de afstand van de buur tot nu toe, dan wordt dat de nieuwe afstand, wordt de knoop onthouden als de weg erheen, en gaat de buur in de wachtrij als hij er nog niet in zat. Als de wachtrij leeg is, heeft elke bereikbare knoop zijn kortste afstand.
Waarom de dichtstbijzijnde knoop definitief is
Als een knoop de dichtstbijzijnde in de wachtrij is, moet elke andere weg ernaartoe het afgewerkte deel van de graaf verlaten via een knoop in de wachtrij, die minstens zo ver weg ligt, en daarna kanten optellen die niet negatief kunnen zijn. Geen andere weg kan dus korter zijn. Daarom is een doel ook pas zeker als het uit de wachtrij wordt genomen, niet als het voor het eerst wordt bereikt, en daarom faalt het algoritme van Dijkstra met negatieve kanten: daar is het algoritme van Bellman–Ford nodig. Als elke kant lengte 1 heeft, doet het algoritme van Dijkstra hetzelfde als breedte-eerst zoeken.
Veelgestelde vragen
Wat is het algoritme van Dijkstra?
Een manier om de kortste paden te vinden van één startknoop naar alle andere knopen in een graaf waarvan de kanten een lengte van nul of meer hebben. Het neemt steeds de dichtstbijzijnde knoop die nog niet klaar is, maakt de afstand definitief en gebruikt de kanten om de afstanden van de buren te verkorten.
Waarom werkt het algoritme van Dijkstra niet met negatieve kanten?
Het maakt de afstand van een knoop definitief zodra die knoop de dichtstbijzijnde in de wachtrij is. Een negatieve kant die later wordt gevonden, kan nog via een kortere weg naar die knoop terugleiden, dus de definitieve afstand kan fout zijn. Het algoritme van Bellman–Ford kan wel met negatieve kanten omgaan, zolang er geen cyclus is met een negatief totaal.
Wat is het verschil tussen Dijkstra en BFS?
Breedte-eerst zoeken telt kanten en gebruikt een gewone wachtrij. Het algoritme van Dijkstra telt de lengtes van kanten op en gebruikt een prioriteitswachtrij die altijd de dichtstbijzijnde knoop geeft. Als elke kant lengte 1 heeft, vinden beide dezelfde afstanden.
Hoe snel is het algoritme van Dijkstra?
Met een binaire heap als prioriteitswachtrij groeit het werk met (V + E) log V voor V knopen en E kanten. Met een Fibonacci-heap is het E + V log V. De app houdt de wachtrij bij als een gesorteerde lijst; dat is makkelijk te tonen en prima voor kleine grafen.
Wordt mijn graaf ergens heen gestuurd?
Nee. De graaf wordt in je browser gemaakt en doorzocht, en je laatste instellingen blijven in de lokale opslag van deze browser.
Klaar om het te proberen?
Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.
Ga naar Editor