Shortest Path

Wat is shortest path?

Shortest path (kortste pad) is het pad tussen twee punten in een netwerk met de laagste totale kosten. Dat netwerk, in de informatica een graaf genoemd, bestaat uit knooppunten (bijvoorbeeld kruispunten of steden) en verbindingen daartussen met een gewicht: afstand, reistijd of kosten. Het kortste pad is de route waarbij de som van die gewichten minimaal is. Het is een van de klassieke optimalisatieproblemen in de informatica.

Hoe werkt het?

Speciale algoritmen zoeken het kortste pad zonder alle mogelijke routes door te rekenen, wat bij grote netwerken praktisch onmogelijk zou zijn. Het bekendste is Dijkstra’s algoritme uit 1956, bedacht door de Nederlandse informaticus Edsger Dijkstra. Het werkt vanaf het startpunt stap voor stap naar buiten en legt steeds de kortste afstand tot elk bereikt knooppunt vast. Varianten zoals A* gebruiken een slimme schatting van de resterende afstand om sneller bij het doel te komen; het Bellman-Ford-algoritme kan ook overweg met negatieve gewichten.

Wat heb je eraan als bedrijf?

Elke navigatie-app draait op kortstepad-algoritmen, en dat geldt ook voor routeplanning in de logistiek: bezorgroutes, ritplanning en netwerkoptimalisatie. Ook buiten transport duikt het op, bijvoorbeeld bij het routeren van dataverkeer in netwerken of het vinden van verbanden in een kennisnetwerk. Voor de meeste bedrijven zit deze techniek kant-en-klaar in software; je hoeft hem niet zelf te bouwen om ervan te profiteren.

Gerelateerde begrippen

Het kortste pad speelt zich af in netwerken, net als graph neural networks en de knowledge graph. Het is een vorm van optimalisatie, een familie waartoe ook het bredere begrip algorithm behoort.