10 Opus 5.5 Agents Discover Shortest Path Algorithm Surpassing Dijkstra in 15 Hours

The shortest path problem is a classic challenge in graph theory, underpinning modern navigation, internet routing, logistics, and countless other real-world applications. In 1959, Dutch computer scientist Edsger Dijkstra proposed an algorithm with a complexity of O(m + n log n), which remained the gold standard for the next 65 years and was used ubiquitously.

In 2025, a team from Tsinghua University, Stanford, and the Max Planck Institute finally surpassed it with an O(m log^{2/3} n) bound. However, the advantage of their solution only manifests on sufficiently dense graphs (where the number of edges m ≥ the number of vertices n). On sparse graphs, Dijkstra’s algorithm remained superior.

Vals AI decided to test the new Opus 5.5 model specifically on this unbroken range (blog post). They launched 10 agents, assigned them the task, and provided a "bulletin board" for them to exchange ideas and cooperate.

As a result, within 15 hours and 733 messages, the agents derived the C-HD algorithm and formally verified it. This is the first proven improvement specifically in the sparse zone where Dijkstra was still the best: at m ≈ n·log^{3/4}n, C-HD achieves O(n·log^{11/12}n) compared to Dijkstra’s O(n log n). At n = 2^1000, the gain is approximately 1.78x and grows with the graph size.

However, despite the impressive claim and the existence of a proof in Lean, there is no talk of practical speedup yet, as the estimates above are asymptotic. The algorithm has not yet been benchmarked on real-world graphs. In other words, while one curve is guaranteed to overtake the other as n → ∞, the crossover point in practice may only occur at enormous n values, and on any realistic graph, Dijkstra will likely still be faster despite having worse asymptotics. This part remains to be verified.