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.
Aún no hay comentarios.