Waarom is dit belangrijk?
Planners kunnen de snelste of de zuinigste weg tussen twee plaatsen laten berekenen, ook wanneer een kaart heel veel wegen telt. In het vervoer gebruiken verkeersmodellen die berekening om ritten voor auto's en schepen vooraf te plannen. Voor reizigers en chauffeurs levert dat een route op die tijd of energie spaart, maar de uitkomst klopt alleen als de kaart actueel is en files of stremmingen meetellen.
Zo werkt het in de praktijk
Het algoritme van Dijkstra zoekt een pad voor een robot, van een startpunt naar een doel. De ruimte is dan een netwerk van plekken. Elke stap krijgt een kost, zoals de afstand.
Onderzoek richt zich op een kortere rekentijd bij grote netwerken. Fredman en Tarjan koppelden het algoritme in 1984 aan een Fibonacci-heap, een wachtrij voor de kleinste afstand. Met voorberekeningen, zoals contractiehiërarchieën die het netwerk vooraf vereenvoudigen, wordt zoeken op grote grafen sneller.
Het algoritme is een greedy methode, die steeds de nu goedkoopste stap kiest. In de kunstmatige intelligentie heet die aanpak uniform-cost search, zoeken op totale kost. Het algoritme van Johnson gebruikt die stap nadat de gewichten zijn herschaald.




