El algoritmo de Dijkstra

El algoritmo de Dijkstra encuentra el camino más corto entre un punto de partida y todos los demás puntos de una red cuyas conexiones tienen un coste no negativo: kilómetros entre ciudades, milisegundos entre routers, minutos entre paradas de metro. Lo publicó Edsger W. Dijkstra en 1959 en tres páginas, y sigue siendo el procedimiento que hay debajo de la mayoría de los navegadores, de los protocolos que encaminan el tráfico de internet y de casi cualquier sistema que tenga que responder a la pregunta «¿por dónde?». Su idea es tan sencilla que se puede ejecutar a mano sobre un mapa, y la figura de esta página está hecha para eso.

La regla es una sola, repetida. Se lleva una lista de distancias provisionales, que al empezar son cero para el origen e infinito para todos los demás. En cada paso se toma, de entre los nodos que aún no están fijados, el que tiene la distancia provisional más pequeña, y se declara fijada: ya no puede mejorar. Después se miran sus vecinos y, para cada uno, se comprueba si llegar a él pasando por el nodo recién fijado sale más barato que la distancia provisional que tenía; si es así, se apunta la nueva. Cuando el nodo que se fija es el destino, se ha terminado, y el camino se reconstruye hacia atrás siguiendo, desde cada nodo, el vecino por el que le llegó su mejor distancia.

Lo que hay que ver en la figura es por qué un nodo, una vez fijado, no puede mejorar. Cuando sale de la cola, su distancia provisional es la menor de todas las pendientes. Cualquier otro camino hasta él tendría que pasar por algún nodo todavía no fijado, y todos esos nodos están, por definición, al menos tan lejos como él. Como las conexiones no restan —eso es lo que significa que los costes sean no negativos—, alargar el recorrido a partir de ahí no puede acortarlo. Por eso la cola es el corazón del algoritmo y por eso la lectura de la figura la muestra en cada paso: el orden en que salen los nodos es el orden creciente de sus distancias definitivas, y lo que parece una búsqueda por el grafo es en realidad una onda que se expande desde el origen y va alcanzando los nodos por distancia.

Esa misma condición marca el límite del método. Si alguna conexión tiene coste negativo —cosa que no ocurre en mapas, pero sí en problemas de finanzas o en grafos que codifican ganancias como costes negativos—, un nodo ya fijado podría mejorarse más tarde, y Dijkstra dará respuestas equivocadas sin avisar. Para esos casos existen algoritmos más lentos, como el de Bellman-Ford, que revisan todas las conexiones varias veces. La otra limitación es que el algoritmo, en su forma original, explora en todas las direcciones por igual: para ir de Madrid a Barcelona calcula también la distancia a Badajoz, porque Badajoz está más cerca que Barcelona y sale antes de la cola. En la figura se ve cuando el destino está al otro extremo del mapa: la mitad de los nodos se fijan antes de llegar a él.

Dijkstra contó en varias ocasiones cómo se le ocurrió. En 1956 trabajaba en el Centro Matemático de Ámsterdam y tenía que preparar una demostración pública del ARMAC, el nuevo ordenador del centro, con un problema que un público no especializado pudiera entender: el camino más corto entre dos de las sesenta y cuatro ciudades de un mapa de los Países Bajos. Según relató en una entrevista de 2001 publicada por Communications of the ACM en 2010, diseñó el algoritmo una mañana en la terraza de un café, tomando un café con su prometida, en unos veinte minutos y sin papel ni lápiz, y añadió que una de las razones de su elegancia era precisamente que se había pensado sin escribir. No lo publicó hasta 1959, y lo hizo casi como una nota al margen, en el primer volumen de una revista nueva, porque en la época los algoritmos apenas se consideraban material publicable.

La eficiencia del algoritmo depende de cómo se organice la cola. La versión de 1959 recorría toda la lista de nodos para encontrar el más cercano en cada paso, lo que para una red de n nodos supone un tiempo proporcional a n². Con un montículo binario, que es la estructura que la figura simula con sus fichas ordenadas, el coste baja a algo proporcional al número de conexiones multiplicado por el logaritmo del número de nodos. Michael Fredman y Robert Tarjan introdujeron en 1984 los montículos de Fibonacci, que llevan el coste teórico a su mínimo conocido para este tipo de algoritmos, aunque en la práctica los montículos binarios suelen ser igual de rápidos por ser más simples.

Sobre Dijkstra se construyó lo que vino después. El algoritmo A*, propuesto por Peter Hart, Nils Nilsson y Bertram Raphael en 1968 para el robot Shakey del instituto de investigación de Stanford, añade a la distancia provisional de cada nodo una estimación de lo que le falta hasta el destino, de manera que la onda se expande preferentemente hacia donde interesa; es el algoritmo de los videojuegos y de la robótica. Para los mapas de carreteras de un continente, con decenas de millones de nodos, ni siquiera eso basta, y desde 2008 los navegadores usan técnicas como las jerarquías de contracción de Robert Geisberger y sus colegas, que preprocesan la red una vez para poder responder después cualquier consulta en menos de un milisegundo. Debajo de todas ellas, en algún nivel, sigue ejecutándose la regla de la terraza del café: sacar el más cercano, fijarlo, revisar a sus vecinos.