Opus 5.5 has for the first time made a breakthrough in the shortest path problem of the Dijkstra algorithm.

Stunning! Opus 5.5 has subverted Dijkstra's shortest path algorithm for the first time ever!

Just a moment ago, Vals AI unveiled a landmark breakthrough that is set to be etched into the annals of computer science history.

They tasked 10 Claude Opus 5.5 Agents to challenge Dijkstra, the classic algorithm for undergraduate computer science programs, and successfully discovered a faster pathfinding approach.

For everyone who has studied computer science, the Dijkstra algorithm is a sacred, untouchable name.

It is the cornerstone of computer science. Generations of top scientists have poured countless efforts into it, exploring for decades to push its optimization to the absolute limit.

For this kind of "classic problem" that has been thoroughly studied by humans, making even one step of further progress is as difficult as climbing to the sky.

This is not an engineering problem that can be solved by "making the code a little more elegant". It requires a proof from the underlying mathematics: the new algorithm is indeed faster even under an infinitely large data scale.

And then, the miracle happened!

The Vals AI team placed 10 Opus 5.5 agents in a sandbox, where they could communicate on a virtual message board, pick holes in each other's work, and even "have fierce arguments" over certain technical routes.

After 15 hours, 733 records of intense discussions were left on the message board.

15 hours later, they submitted their results. This group of AIs not only proposed a brand new algorithm named C-HD, but also provided a Lean formal proof consisting of 289 files, which was directly sent to the Lean Kernel for machine verification and passed at one go!

The algorithm community was shaken instantly.

Some people exclaimed: "Research that used to take humans several years to carry out trial and error can now be replicated in parallel by Agents in half a day?"

Dijkstra on the altar of algorithms

The Dijkstra algorithm is an extremely simple yet extremely core problem.

Given a graph with several vertices and directed edges connecting them, each edge has a non-negative real weight. Starting from a certain starting point, you need to find the path with the minimum total weight to every other vertex in the graph, or determine that such a path is unreachable.

All internal operations, such as counting node accesses and storing intermediate distances, are counted into the running time.

In this field, the Dijkstra algorithm proposed by Edsger W. Dijkstra in 1959 still exists like a god to this day.

With a suitable priority queue data structure (such as a Fibonacci heap), the time complexity of the Dijkstra algorithm reaches the perfect

, where n ≥ 2 is the number of vertices and m is the number of edges.

At the current theoretical frontier, when m ≥ n, other breakthroughs have also been made.

For example, a landmark paper in 2025 pushed the complexity to

, followed by subsequent research in 2026 that reached

.

However, when the density of the graph is in a certain intermediate state, Dijkstra is still the unshakable king.

This time, the ultimate difficult problem humans posed to AI is —

To design a shortest path algorithm faster than Dijkstra, and it must be proven with the Lean formal mathematical language.

15 hours, 733 in-depth discussions: How 10 AIs "argued out" the C-HD algorithm

If the previous Hugging Face incident and the solving of the NS problem taught us anything, it is that agents can drastically reduce the time humans spend making progress on difficult problems.

The most effective way to get Agents to work together is to give them a "communication forum", where more people bring greater strength.

In the experiment, humans launched 10 Claude Opus 5.5 Agent instances, cranking their "effort value" to the maximum.

These 10 Agents had initial division of labor roles, but were granted extremely high autonomy: they could reorganize work at any time, share new discoveries, question each other, and shift computing power to the most promising directions.

Then, humans gave them a long list of strict prompts.

1. Must find the exact shortest path on a directed graph with non-negative real weights.

2. Must achieve a substantial improvement in theoretical complexity.

3. Must provide a complete, reproducible Lean mathematical proof.

4. Must be compared with the latest top-tier human papers from 2025 and 2026 (such as the cutting-edge achievement that reduces the complexity to O(m \log^{2/3} n)).

5. Must record all failed attempts to prevent other Agents from falling into the same traps.

6. Before announcing success, two independent "AI peer reviews" must be completed.

Then, during the 15-hour "closed-door operation", these 10 Opus 5.5 started running frantically, like a special forces unit, demonstrating amazing collaborative capabilities.

When they found a dead end that led nowhere, they would immediately shout on the message board: "This path doesn't work, don't try it!" If one AI put forward a new idea, other AIs would act like ruthless reviewers, frantically looking for loopholes.

Eventually, they delivered the final result — the C-HD algorithm.

Why does C-HD dare to challenge Dijkstra?

The classic Dijkstra algorithm adopts a greedy strategy: each time it honestly picks the unvisited vertex with the closest distance from the current set, and then expands outward.

After using suitable data structures such as a Fibonacci heap, its time complexity can be stably maintained at O(m + n \log n).

But the 10 Claude agents thought this was not fast enough!

The C-HD algorithm they developed has made fundamental innovations in its strategy.

A netizen specifically asked Opus 5.5 to draw a principle comparison diagram: in the world of C-HD, the algorithm no longer only focuses on a single closest point like Dijkstra does, but marks a number of yellow "pivot points"

They introduced an ingenious strategy based on heuristic decomposition, the specific concept of which is as follows:

1. Start from the source point and the current vertex boundary.

2. Run a bounded local search along the outgoing edges.

3. Include newly encountered vertices in the search limit: even if an edge does not improve the distance estimate, those unexplored leaf nodes will also be counted.

4. Use the resulting search tree and "pivots" to organize recursive work.

Even more impressively, the AIs also designed strict "local invariants" for this algorithm — that is, mathematical rules that must remain true after each update.

By carefully removing invalid edges and limiting local search, C-HD minimizes redundant searches and useless operations on data structures to the extreme.

As a result, within a specific range of sparse graphs, the complexity of classic Dijkstra is:

.

And the C-HD algorithm forcibly reduces it to:

Specifically, the C-HD algorithm establishes the following amazing upper bound of complexity —

where the verification range is

.

In comparison, the leading term ratio between Dijkstra's

and C-HD is

.

Within this specific sparse graph interval, C-HD has achieved a rigorous asymptotic complexity surpass!

Next, they completed the most valuable part: formal verification.

The 10 Claude agents submitted 289 Lean files, constructing the complete theorem:

-- From namespace Frontier.CHD.Final:

theorem chd_CHDTarget : GateCTarget.CHDTarget GateCCalc.F :=

⟨chdProgram, chd_exact_within.