Dijkstra algoritme (1)
algoritme van Dijkstra
De Nederlandse wiskundige Edsger Dijkstra (1930-2002) werkte een algoritme uit om in een graaf het kortste pad tussen twee punten te vinden. Het wordt heel verstaanbaar uitgelegd op ode aan Dijkstra.
Het idee van dit algoritme is dat we de knopen labelen en daarbij telkens het kleinste label kiezen.
We maken daarbij tijdelijke en permanente labels. Een tijdelijk label geeft de kortste afstand van het beginpunt tot die knoop, die we tot dan toe gevonden hebben.
Bij iedere stap die we doen kan dit tijdelijke label kleiner worden. We maken een tijdelijk label permanent wanneer we vaststellen dat er geen korter pad naar die knoop bestaat.
Volgende applet berekent het korste pad tussen A en G volgens het algoritme van Dijkstra.