10 agentes de Opus 5.5 descubren un algoritmo de ruta más corta que supera a Dijkstra en 15 horas

El problema de la ruta más corta es un desafío clásico en la teoría de grafos, fundamental para navegadores, enrutamiento de internet, logística y muchas otras aplicaciones modernas. En 1959, el informático holandés Edsger Dijkstra propuso un algoritmo con una complejidad de O(m + n log n), que permaneció como el estándar de oro durante los siguientes 65 años y se utilizó prácticamente en todas partes.

En 2025, un equipo de Tsinghua, Stanford y el Instituto Max Planck logró superarlo por primera vez con una cota de O(m log^{2/3} n). Sin embargo, la ventaja de su solución solo se manifiesta en grafos suficientemente densos (donde el número de aristas m ≥ el número de vértices n). En grafos dispersos, el algoritmo de Dijkstra seguía siendo superior.

Vals AI decidió probar el nuevo modelo Opus 5.5 específicamente en este rango no superado (entrada del blog). Lanzaron 10 agentes, les asignaron la tarea y les proporcionaron un "tablón de anuncios" para que pudieran intercambiar ideas y cooperar.

Como resultado, en 15 horas y 733 mensajes, los agentes obtuvieron el algoritmo C-HD y lo verificaron formalmente. Esta es la primera mejora probada específicamente en esta zona dispersa, donde Dijkstra seguía siendo el mejor: en m ≈ n·log^{3/4}n, C-HD logra O(n·log^{11/12}n) frente a O(n log n) de Dijkstra. Con n = 2^1000, la ganancia es de ~1,78x y crece con el tamaño del grafo.

Sin embargo, a pesar de la impresionante afirmación y la existencia de una prueba en Lean, aún no se habla de una aceleración práctica, ya que las estimaciones son asintóticas. El algoritmo aún no se ha sometido a pruebas de referencia en grafos reales. Es decir, aunque a medida que n → ∞ una curva superará garantizando a la otra, en la práctica el punto de cruce puede ocurrir solo con valores enormes de n, y en cualquier grafo realista, Dijkstra seguirá siendo más rápido a pesar de tener una asintótica peor. Esta parte aún está por verificar.