Adiós Dijkstra: el algoritmo de Tsinghua que rompe 66 años de teoría y gana el Best Paper de STOC 2025

⏱️ Lectura: 15 min

Durante sesenta y seis años, el algoritmo más enseñado en cualquier curso universitario de algoritmos —el de Edsger Dijkstra, publicado en 1959— fue tratado como el techo teórico para encontrar caminos más cortos en un grafo. Cualquier libro de texto desde Introduction to Algorithms (CLRS) hasta los manuales de programación competitiva afirma que la cota O(m + n log n) es lo mejor que la humanidad sabe hacer cuando los pesos pueden ser cualquier número real no negativo y solo se permiten comparaciones y sumas. Esa creencia se rompió en 2025. Cinco investigadores —Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu y Longhui Yin, liderados por Duan en el Institute for Interdisciplinary Information Sciences (IIIS) de la Universidad de Tsinghua— publicaron en arXiv el 23 de abril de 2025 un paper titulado Breaking the Sorting Barrier for Directed Single-Source Shortest Paths. El paper presenta un algoritmo determinista con tiempo O(m log^(2/3) n) que, en grafos dispersos, es estrictamente más rápido que Dijkstra. En junio de 2025 ganó el Best Paper Award del 57th ACM Symposium on Theory of Computing (STOC 2025), el galardón más alto que existe en computación teórica. Este artículo explica qué es la «barrera del sorting» que cayó, qué hace exactamente la nueva técnica BMSSP, por qué Dijkstra dejó de ser óptimo, y qué cambia (y qué no) para los desarrolladores que escribimos código de rutas todos los días.

📑 En este artículo

1. Por qué Dijkstra fue intocable durante 66 años
2. El modelo de comparación-adición y por qué importa
3. La idea central: BMSSP, frontier reduction y pivots
4. Cómo se compara: la tabla que importa
5. Por qué la noticia es enorme aunque la mejora práctica sea modesta
6. Quiénes son los autores
7. Qué cambia para los desarrolladores que escribimos código de rutas
8. Aplicaciones reales donde la noticia importa más
9. Lo que queda abierto
10. Por qué este paper merece tu atención
11. Fuentes
    1. 📚 Artículos relacionados

Por qué Dijkstra fue intocable durante 66 años

En 1956, mientras tomaba café con su esposa María en un mall de Ámsterdam, Edsger Dijkstra inventó en veinte minutos uno de los algoritmos más influyentes de la informática moderna. La versión que publicó tres años después, en Numerische Mathematik en 1959, resolvía el problema single-source shortest paths (SSSP): dado un grafo dirigido con pesos no negativos en sus aristas, encontrar el camino más corto desde un vértice raíz hasta todos los demás. El algoritmo es elegante porque traduce un problema combinatorio en uno de prioridad: en cada paso, extraer el vértice «más cercano» todavía no procesado, relajar sus aristas, y repetir.

Esa elegancia esconde una limitación que la teoría tardó décadas en formular con rigor. La operación «extraer el vértice más cercano» es esencialmente un mínimo en una cola de prioridad, y mantener esa cola ordenada cuesta tiempo. Con un heap binario, el costo es O((m + n) log n). Con un heap de Fibonacci —descubierto por Fredman y Tarjan en 1984— baja a O(m + n log n). Y ahí parecía haberse estancado el problema durante cuarenta años. Mejoras posteriores (Thorup, Pettie, Spira) atacaban casos especiales —enteros con cota, grafos no dirigidos, modelos de RAM con palabras—, pero el caso directed graphs con pesos reales en el modelo de comparación-adición seguía con O(m + n log n) como cota superior y la sospecha generalizada de que Dijkstra era óptimo.

Esa sospecha se reforzó en 2024 cuando Haeupler, Hladík, Rozhoň, Tarjan y otros publicaron resultados de optimalidad universal de Dijkstra sobre heaps «beyond-worst-case», mostrando que con la estructura de datos correcta, Dijkstra alcanza el mejor tiempo posible para cualquier instancia particular comparado con cualquier otro algoritmo basado en colas de prioridad. La conclusión natural fue: si querés batir a Dijkstra, no usés colas de prioridad.

El modelo de comparación-adición y por qué importa

Para entender la magnitud del resultado de Tsinghua hay que precisar la regla del juego. El modelo de comparación-adición es un marco teórico en el que un algoritmo solo puede manipular los pesos de las aristas mediante dos operaciones: compararlos entre sí (¿es a mayor que b?) y sumarlos (¿cuánto vale a + b?). No se permiten multiplicaciones ni operaciones de bits, ni asumir que los pesos son enteros pequeños que caben en una palabra de máquina. Es el modelo más limpio para razonar sobre algoritmos puramente combinatorios.

En este modelo, el costo del trabajo se mide en el número de comparaciones y sumas que el algoritmo realiza. Y aquí aparece la barrera del sorting: si querés ordenar n números reales —incluso los costos finales hacia los n vértices destino— necesitás Ω(n log n) comparaciones, sin atajos. Dijkstra implícitamente ordena: al extraer vértices uno por uno por distancia creciente, está construyendo el orden total de los costos. Por eso la cota O(m + n log n) parecía irreductible: el sort estaba «embedded» en la estructura del problema.

La pregunta abierta era si realmente necesitabas ordenar todo. Quizá fuera posible calcular las distancias correctas sin haber producido nunca, ni siquiera implícitamente, el orden total entre ellas. Esa fue la pregunta que el equipo de Duan respondió: sí.

La idea central: BMSSP, frontier reduction y pivots

El algoritmo de Tsinghua se llama BMSSP (Bounded Multi-Source Shortest Paths) y opera mediante una recursión divide-and-conquer que evita explícitamente cualquier sort global. La descripción técnica está en las 17 páginas del PDF en arXiv, pero la intuición se puede transmitir en cuatro pasos.

Primer paso: cluster de la frontera, no vértice por vértice. En cada iteración, Dijkstra extrae un solo vértice —el de menor distancia tentativa— y lo procesa. BMSSP en cambio agrupa la «frontera» (los vértices candidatos a ser procesados a continuación) en clusters de tamaño aproximado Θ(log^(2/3) n). Procesar un cluster entero a la vez amortiza el costo del descubrimiento de candidatos.

Segundo paso: pivot selection en lugar de min-heap. Para decidir qué cluster avanzar primero, BMSSP no busca el mínimo absoluto. Selecciona pivots —vértices representativos del cluster, elegidos con una estrategia de tipo quickselect— y particiona el problema según comparaciones contra esos pivots. Esto reemplaza la operación «extract-min» por algo más cercano a «select-quantile», que tiene mejor amortización al trabajar con conjuntos.

Tercer paso: orden parcial, nunca total. En ningún momento BMSSP construye el orden total de los costos. Mantiene un orden parcial suficiente para garantizar correctitud: cuando dos vértices están en clusters distintos, el algoritmo «sabe» cuál procesar primero, pero dentro de un cluster no se molesta en ordenarlos. Esa es la grieta que evita la barrera del sorting: si nunca producís el orden total, nunca pagaste su costo.

Cuarto paso: hibridación con Bellman-Ford en clusters densos. Cuando un cluster tiene mucha estructura interna (muchas aristas internas relativas a su tamaño), el algoritmo cambia a una variante de Bellman-Ford —la herramienta clásica para shortest paths con pesos negativos— solo dentro de ese cluster. Es un híbrido oportunista: Dijkstra-like entre clusters, Bellman-Ford-like dentro de los densos.

El resultado neto es O(m log^(2/3) n), una cota estrictamente mejor que O(m + n log n) cuando el grafo es disperso (m cercano a n, no muy denso). En grafos densos —donde m se aproxima a n²— Dijkstra sigue ganando.

Cómo se compara: la tabla que importa

Algoritmo	Año	Tiempo	Determinismo	Modelo
Dijkstra (binary heap)	1959	O((m + n) log n)	Determinista	Comparación-adición
Dijkstra (Fibonacci heap, Fredman & Tarjan)	1984	O(m + n log n)	Determinista	Comparación-adición
Thorup (RAM model, integer weights)	1999	O(m + n)	Determinista	RAM con palabras
Pettie	2004	O(m + n log log n) (no dirigido)	Determinista	Comparación-adición
Duan, Mao, Mao, Shu, Yin (Tsinghua)	2025	O(m log^(2/3) n)	Determinista	Comparación-adición

Para que se aprecie en cifras concretas: en un grafo con n = 1,000,000 vértices y m = 5,000,000 aristas (un grafo de routing realista de un ISP), log n ≈ 20 y log^(2/3) n ≈ 7.4. Las operaciones rondan:

• Dijkstra clásico (Fibonacci heap): m + n log n ≈ 5M + 20M = 25M operaciones
• BMSSP: m log^(2/3) n ≈ 5M × 7.4 = 37M operaciones

Espera — en este caso concreto BMSSP no es más rápido. Esto requiere precisión: la mejora en m log^(2/3) n vs m + n log n se manifiesta cuando m es mucho menor que n log n, es decir, en grafos muy dispersos. La tabla de complejidades asintóticas no se traduce automáticamente a velocidad práctica para todas las instancias. El paper habla de una cota teórica en el modelo asintótico; el impacto práctico depende de la densidad del grafo, las constantes ocultas, la calidad de la implementación y los efectos de caché que ningún análisis asintótico captura.

Por qué la noticia es enorme aunque la mejora práctica sea modesta

Aquí es donde la noticia educativa importa más que la velocidad bruta. Lo que el paper de Tsinghua demuestra no es que cualquiera deba reescribir su código de routing en producción mañana. Lo que demuestra es algo más profundo: Dijkstra no es óptimo.

Esa frase, en una sola línea, cierra una conjetura abierta de seis décadas y abre tres preguntas nuevas que ahora son los problemas calientes en el campo:

1. ¿Cuál es el verdadero límite inferior para SSSP en el modelo de comparación-adición? Antes del paper de Duan, muchos investigadores razonaban «Dijkstra es óptimo, lower bound es Ω(m + n log n)». Ahora ese razonamiento está roto. La cota inferior real podría ser O(m), o algo intermedio. La búsqueda comenzó.
2. ¿Se puede hacer aún más rápido sin determinismo? El paper de Tsinghua es determinista. Versiones randomizadas existían antes con cotas similares para casos especiales; la cuestión ahora es si randomización compra algo adicional para el caso general.
3. ¿La técnica BMSSP se generaliza? Frontier reduction + pivot selection puede ser una herramienta útil para otros problemas de grafos: max-flow, min-cost flow, coupling, network simplex. La maquinaria es portable.

El reconocimiento del STOC Best Paper Award 2025 —otorgado por el comité del simposio más prestigioso en computación teórica— refleja exactamente este peso: no es un avance incremental, es un cambio de paradigma sobre lo que se puede esperar de algoritmos de grafos.

Quiénes son los autores

Ran Duan lidera el grupo. Doctorado por la Universidad de Michigan (2011), postdoctorado en el Max-Planck-Institut für Informatik (2011-2014), profesor en el IIIS de Tsinghua desde su retorno a China. Su perfil institucional lista como áreas de investigación «graph algorithms, data structures, approximate and randomized algorithms, computational complexity». Antes de este resultado ya tenía contribuciones notables en min-cost matching y all-pairs shortest paths.

Jiayi Mao, Xiao Mao, Xinkai Shu y Longhui Yin son investigadores afiliados al mismo instituto, probablemente PhD students en el momento de la publicación. La diversidad de coautores y el peso del grupo —cinco investigadores produciendo un único paper en un problema clásico— es típico del trabajo de algoritmos teóricos de alto nivel: cada autor aporta una pieza de la maquinaria, y la composición final solo emerge cuando todas las piezas encajan.

Qué cambia para los desarrolladores que escribimos código de rutas

La pregunta práctica es directa: si trabajás en un equipo de routing, navegación, logística o redes, ¿deberías reemplazar Dijkstra por BMSSP en producción? La respuesta es no, todavía no. Pero hay matices importantes.

Para sistemas en producción ahora. Los routers de Cisco, los protocolos OSPF e IS-IS, el motor de rutas de Google Maps, el algoritmo A en motores de juegos —todos siguen siendo apropiados con Dijkstra y heuristicas como A o bidirectional Dijkstra. La razón es operacional: los grafos de routing reales tienen densidad media, los heaps de Fibonacci en producción son raros (binary heaps suficientes), y las constantes hidden en BMSSP no se han optimizado para hardware moderno con caché L1/L2/L3. Las implementaciones de referencia disponibles en GitHub son didácticas, no production-grade.

Para investigadores y estudiantes de algoritmos. El paper es lectura obligatoria. La técnica de frontier reduction + pivot partition es generalizable. Si trabajás en problemas de grafos con cotas asintóticas que parecen estar bloqueadas por sorting implícito (max flow, min-cost flow, network design), vale la pena estudiarla.

Para los que enseñan. Los cursos de algoritmos van a cambiar. Hace décadas que la cota O(m + n log n) se enseña como «lo mejor conocido»; las próximas ediciones de los textbooks van a tener que mencionar el resultado de Tsinghua como nota al pie, y eventualmente como caso de estudio. La pedagogía de SSSP ya no termina en Dijkstra.

Para arquitectos de sistemas distribuidos. El paradigma «cluster + pivot» tiene similitudes con técnicas de MapReduce y bulk-synchronous parallel (BSP) computing: trabajás batch sobre conjuntos en lugar de elemento a elemento. Esa proximidad sugiere que BMSSP puede tener variantes paralelas atractivas para grafos masivos —web graph, social graph, knowledge graph—. Esa es la frontera natural de investigación aplicada.

Aplicaciones reales donde la noticia importa más

Si reducimos esto a casos donde la reducción asintótica realmente cambia ingeniería, hay tres dominios donde el equipo de implementación práctica vale la pena seguir.

Routing en redes de gran escala. Los protocolos OSPF e IS-IS recalculan SSSP en cada cambio topológico. Un ISP grande maneja decenas de miles de prefijos y cientos de routers; la reducción asintótica puede traducirse en latencia de convergencia menor frente a flapping de enlaces. Cisco y Juniper han mostrado interés histórico en mejoras algorítmicas de SSSP.

GPS y mapas a escala continental. Google Maps, Apple Maps, OpenStreetMap-based engines (OSRM, Valhalla, GraphHopper) usan variantes de Dijkstra con preprocesamiento (Contraction Hierarchies, Hub Labels, ALT). El preprocesamiento es lo que les da velocidad sub-segundo en mapas globales; cualquier mejora del SSSP base se compone con esos preprocesos. BMSSP encajaría como base de un sistema CH si se logra una implementación cache-friendly.

Bioinformática y análisis de redes. Redes de interacción de proteínas, redes metabólicas, redes filogenéticas — todos usan SSSP en pipelines diarios. Las constantes prácticas no son tan críticas como en routing en tiempo real, pero la cobertura de instancias diversas hace que cualquier reducción asintótica sea bienvenida.

Lo que queda abierto

El paper de Duan resuelve una pregunta y abre tres. La cota inferior real para SSSP en el modelo de comparación-adición sigue sin conocerse. Es plausible que el verdadero límite sea cercano a Ω(m), pero ningún paper ha cerrado la brecha entre Ω(m) (trivialmente requerido para leer todas las aristas) y O(m log^(2/3) n) (la cota actual). Cerrar esa brecha en cualquier dirección —encontrar un algoritmo aún más rápido o demostrar que no es posible— sería otro Best Paper de STOC.

La segunda pregunta abierta es si el resultado se extiende a grafos no dirigidos. El paper de Tsinghua aplica a grafos dirigidos; para grafos no dirigidos hay resultados independientes (Pettie 2004 ya tenía O(m + n log log n)) que el nuevo paper no supera. La unificación de ambos casos en un único framework algorítmico es trabajo aún por hacer.

La tercera, quizá la más práctica, es si las técnicas de frontier reduction + pivot se pueden ingenierizar en código real con buen comportamiento de caché, paralelismo y SIMD. Hasta ahora las implementaciones disponibles son demostrativas. La industria espera una versión con benchmarks frente a Boost Graph Library y LEMON sobre grafos del orden de cientos de millones de aristas.

Por qué este paper merece tu atención

Si trabajás en software, este resultado importa por tres razones que trascienden lo algorítmico.

Primera: las verdades que damos por sentado pueden no serlo. Dijkstra fue tratado como óptimo durante 66 años. La conjetura no se demostró nunca, simplemente nadie había construido el contraejemplo. Esa dinámica —»todos saben que X es cierto pero nadie tiene la prueba»— es un patrón recurrente en informática. Cada vez que veas una afirmación de optimalidad sin lower bound, vale la pena dudar.

Segunda: la teoría sigue avanzando. En tiempos donde la conversación tecnológica está dominada por LLMs, agentes autónomos y stablecoins, es fácil olvidar que la computación teórica sigue produciendo resultados fundacionales. STOC, FOCS, SODA — los simposios que organizan este trabajo — siguen siendo donde se decide qué será posible en treinta años.

Tercera: la ingeniería se beneficia de la teoría incluso cuando la mejora asintótica es marginal. El paper de Tsinghua probablemente no cambie la latencia de tu aplicación mañana. Pero la herramienta conceptual —frontier reduction, pivot partition, hibridación oportunista— es transferible a otros problemas. Si en tu trabajo construís grafos de dependencias, evaluás caminos de migración, optimizás scheduling de tareas, o cualquier cosa con estructura grafo, esta caja de herramientas vale la pena guardar.

El algoritmo de Dijkstra de 1959 sigue siendo un milagro de elegancia y va a seguir enseñándose en primero de carrera. Pero ya no podemos llamarlo óptimo. Y eso, después de 66 años, es una de las noticias más importantes en computación teórica de esta década.

Fuentes

• arXiv — Breaking the Sorting Barrier for Directed Single-Source Shortest Paths (paper completo, 17 páginas)
• arXiv — PDF directo del paper
• IIIS Tsinghua — Perfil de Ran Duan
• ACM — DOI 10.1145/3717823.3718179 (STOC 2025 proceedings, Best Paper Award)
• GitHub — Implementación didáctica en Java de shashipk
• GitHub — Implementación BMSSP de localrivet