Per prima cosa, occorre modellizzare la rete stradale con un grafo G, ossia un insieme di vertici e lati: ogni incrocio tra due strade è un vertice di G e ogni tratto di strada compreso tra due incroci è un lato. A ciascun lato si può assegnare un valore, per esempio una distanza in chilometri o in ore, ottenendo così un grafo pesato. Trovare il cammino minimo tra due vertici (un’origine O e una destinazione Dest) significa allora trovare la successione di lati che collega O a Dest e la cui somma è minima.
Nel 1959, l’informatico olandese Edsger Dijkstra propose a questo scopo un algoritmo molto efficace. L’algoritmo utilizza il principio enunciato dal matematico Richard Bellman, secondo il quale ogni sottocammino di un cammino ottimale è a sua volta ottimale.
In altre parole, se il cammino minimo da O a Dest è O-A-D-E-Dest, allora il cammino minimo da A a E è A-D-E… e viceversa. È quindi possibile trovare il cammino minimo tra l’origine e la destinazione avanzando vertice dopo vertice nel grafo e memorizzando, a ogni iterazione, il cammino minimo che collega l’origine a ciascun vertice del grafo.
