Científicos rompen récord al resolver el problema más antiguo de la computación

...

En el mundo de la informática teórica, hay problemas que parecen inamovibles, como si estuvieran tallados en piedra. Uno de ellos es el de encontrar el camino más corto en un grafo, un rompecabezas que ha desafiado a generaciones de científicos desde los años 50

Autor

Xavier Rivera Martinez el 13/10/2025 12:03 PM.
En ciencia y tecnología y editada el 13/10/2025 12:12 PM.

Hasta ahora, el algoritmo de Dijkstra era considerado la solución definitiva, pero un equipo de investigadores acaba de romper ese paradigma con un enfoque que, irónicamente, parte de lo que muchos consideraban "la opción más tonta".

"Casi podría llamarlo anti-prometedor usar Bellman-Ford, porque parece lo más estúpido que podrías hacer", confesó Mikkel Thorup, uno de los investigadores involucrados. Sin embargo, esa aparente torpeza escondía la clave del avance: Ran Duan y su equipo en la Universidad Tsinghua descubrieron que al aplicar el algoritmo Bellman-Ford de manera selectiva —ejecutándolo solo en pasos estratégicos— podían identificar nodos cruciales que aceleraban el proceso global.

El verdadero giro llegó en marzo de 2024, cuando Yin Tat Mao propuso eliminar un elemento clave que hasta entonces parecía indispensable: la aleatoriedad. Los algoritmos aleatorios son eficientes, pero los investigadores prefieren soluciones deterministas. Mao logró reformular el problema para prescindir de ese componente, lo que permitió al equipo fusionar ideas durante meses de intensas discusiones virtuales.

El avance final vino de un recuerdo: Duan adaptó una técnica de su propio algoritmo de 2018, originalmente diseñado para otro problema de grafos. La estrategia resultante es compleja pero elegante:

Corta el grafo en capas, como lo haría Dijkstra, pero sin explorar toda la frontera en cada paso.
Usa Bellman-Ford para detectar nodos influyentes, avanza desde ellos y luego retoma nodos secundarios.
Evita ordenar distancias en cada capa, esquivando así la barrera computacional que parecía infranqueable.

Lo más sorprendente, según Thorup, es que "esto bien pudo haberse descubierto hace 50 años". La solución no requiere matemáticas exóticas, sino una reorganización ingeniosa de piezas conocidas. Ahora, el equipo ya explora cómo refinar el algoritmo para hacerlo aún más veloz. Como señaló Robert Tarjan, pionero en ciencia computacional, "no creo que este sea el último paso". La puerta para optimizar uno de los problemas fundamentales de la computación acaba de abrirse un poco más.