Un equipo de investigadores liderado por Ran Duan, de la Universidad de Tsinghua, ha presentado un nuevo algoritmo que supera al algoritmo de Dijkstra, estándar durante 65 años para encontrar la ruta más corta en un mapa. Publicado el 31 de julio de 2025 en arXiv, este algoritmo reduce la carga de ordenamiento sin perder precisión en grafos dirigidos con pesos reales no negativos.
El algoritmo de Dijkstra, ideado en 1959 por Edsger Dijkstra, ha sido fundamental en aplicaciones como Google Maps. El nuevo método, basado en una técnica de 'divide y vencerás', selecciona un subconjunto de nodos llamados 'pivotes' y logra reducir drásticamente la cantidad de nodos que deben mantenerse ordenados.
Esto mejora el tiempo total de ejecución respecto al algoritmo de Dijkstra, especialmente en grafos dispersos como redes de transporte urbano o mapas de carreteras. La mejora teórica se nota en contextos donde se requieren muchos cálculos simultáneos, como sistemas de entrega o análisis de redes sociales.
El avance demuestra que aún es posible mejorar algoritmos considerados insuperables y abre una línea de investigación para nuevos enfoques híbridos y eficientes.
Crítica:
El artículo cumple con las expectativas del título al presentar un nuevo algoritmo que desafía 65 años de historia en la resolución de rutas más cortas. La información es densa y específica, con detalles técnicos precisos. Sin embargo, podría profundizar más en las implicaciones prácticas en la industria y su posible implementación en aplicaciones comerciales. El tono es informativo y serio, adecuado para un tema científico.
Comentarios