Un nuevo algoritmo mejora la ruta más corta en grafos, superando a Dijkstra tras 65 años

El problema de encontrar la ruta más corta entre dos puntos en un grafo es uno de los más relevantes en computación y se aplica en tareas cotidianas como los mapas de Google o aplicaciones de transporte. Durante más de seis décadas, el algoritmo de Dijkstra ha sido la solución más eficiente para este desafío. Sin embargo, en julio de 2025, un equipo de investigadores liderado por Ran Duan presentó una nueva solución que mejora significativamente la eficiencia del algoritmo de Dijkstra, especialmente en grafos dispersos. Este avance se debe a un enfoque innovador conocido como reducción de frontera, que combina lo mejor de otros algoritmos previos, como Bellman-Ford, para reducir el tamaño de la frontera de búsqueda sin perder exactitud. Aunque este algoritmo es más eficiente en grafos dispersos, Dijkstra sigue siendo la mejor opción en grafos densos. La mejora no es solo teórica; tiene implicaciones prácticas importantes, como una mejor optimización de rutas en sistemas de transporte, entrega de productos y reducción de latencia en videojuegos. Sin duda, esta mejora marcará un cambio en cómo se abordan los problemas de rutas en las ciencias computacionales.