Para empezar, hay que modelizar la red de carreteras mediante un grafo G, es decir, un conjunto de vértices y aristas: cada cruce entre dos carreteras es un vértice de G y cada tramo de carretera entre dos cruces es una arista. Podemos asignar un valor —por ejemplo, una distancia expresada en kilómetros o una duración en horas— a cada arista para obtener un grafo ponderado. Encontrar el camino más corto entre dos vértices (un origen O y un destino Dest) consiste entonces en hallar la sucesión de aristas que une O con Dest y cuya suma es mínima.
En 1959, el informático neerlandés Edsger Dijkstra propuso un algoritmo muy eficaz para ello. Utiliza el principio enunciado por el matemático Richard Bellman, según el cual cualquier subcamino de un camino óptimo es a su vez óptimo.
Dicho de otro modo, si el camino más corto de O a Dest es O-A-D-E-Dest, entonces el camino más corto de A a E es A-D-E… y recíprocamente. Por tanto, es posible encontrar el camino más corto entre el origen y el destino avanzando vértice a vértice por el grafo y guardando en memoria, en cada iteración, el camino más corto desde el origen hasta cada vértice del grafo.
