Un equipo de investigación de la Universidad de Tsinghua, en colaboración con la Universidad de Stanford, logró un gran avance en términos de complejidad computacional para el problema tradicional de ruta más corta de una sola fuente (single-source shortest path, SSSP). Este trabajo recibió el premio a Best Paper en STOC 2025.
Tradicionalmente, el método más usado ha sido el algoritmo de Dijkstra, con una complejidad temporal de la forma O(m + n log n) (n = número de nodos, m = número de aristas).
El término log n está relacionado con la cola de prioridad (priority queue) o el ordenamiento (sorting), y en los últimos 40 años no había habido mejoras que superaran esa parte.
El nuevo algoritmo redujo la complejidad temporal a O(m · log^(2/3) n).
Como log^(2/3) n crece más lentamente que log n (es decir, aumenta menos que log n), la diferencia se vuelve mayor cuando la cantidad de nodos es muy grande.
18 comentarios
Me trae recuerdos (?) de cuando, a fines de los 2000, trabajaba en una empresa de software de navegación para vehículos desarrollando un módulo de búsqueda de rutas.
Dijkstra es demasiado lento para la búsqueda de rutas en navegación, así que no se usa; en su lugar se usa la búsqueda A* (A Star), una versión mejorada con heurística. Revisando, veo que A* no es un algoritmo SSSP sino SPSP (Single-Pair Shortest Path).
Parece ambiguo decir que superó a los algoritmos rápidos para casos
sparse.No ha pasado tanto desde que se actualizó CLRS, ¿ya van a sacar una nueva edición?
Se siente como si hubiera salido un nuevo álbum, 41 años después, de bandas que aparecieron en el pasado y siguen siendo populares hasta hoy, como The Beatles u Oasis. Primero, sorprende y despierta el interés, jaja.
¿Capaz que EE. UU. ya lo tenía? 😳😳😳
Qué hermoso, uf.
China últimamente está avanzando con fuerza.
Me pregunto cómo terminarán poniéndole nombre al algoritmo.
Seguro alguien va a poner un problema en Baekjoon con esas restricciones muy pronto. Qué emoción.
El clásico Dijkstra de siempre..
Vaya... esto está increíble...
Genial.
Guau......
Sí funciona...
¡Kyaaa~~
Vaya....
Parece que van a tener que agregar esto al contenido de las clases de algoritmos jajaja
Ay...