Dijkstra's algoritme, gepubliceerd door Edsger Dijkstra in 1959, is een krachtige methode voor het vinden van de kortste paden tussen hoekpunten in een grafiek. Dit Instructable bevat de stappen van dit algoritme, u helpen bij het volgen van het algoritme op papier of in een programma ten uitvoer te leggen.
Merk op dat de stappen alleen het kortste pad lengtes opnemen, en sla niet de werkelijke kortste paden langs de hoekpunten. Indien kennis van de samenstelling van de paden is gewenst, stap 2 en 4 kunnen eenvoudig worden aangepast om deze gegevens opslaan in een andere associatieve array: Zie Dijkstra's 1959 papier in Numerische Mathematik voor meer informatie.
Oke, laten we aan de slag! In deze instructies veronderstellen wij hebben we de volgende informatie:
- Een grafiek G
- Een verzameling van hoekpunten V
- Een set van randen E (waar elke rand heeft een niet-negatief gewicht)
- Een uitgangspunt s ∈ V
Merk op dat het "element van" symbool, ∈, geeft aan dat het element aan de linkerkant van het symbool binnen de collectie aan de andere kant van het symbool. S ∈ V geeft bijvoorbeeld aan dat s een element van V is --in dit geval betekent dit dat s is een hoekpunt deel uitmaakt van de grafiek.
Deze aanwijzingen zijn ontworpen voor gebruik door een publiek bekend met de basisprincipes van grafentheorie, verzamelingenleer en gegevensstructuren. Met deze vereiste kennis moet dat alle notatie en gebruikte begrippen relatief eenvoudig voor het publiek zijn.
Voor meer informatie over de details van Dijkstra's algoritme is de Wikipedia-pagina op het een uitstekende bron.
