← @bgSponge

A Faster Shortest Path Algorithm

Summary

Geby Jaff shows that Claude Opus 5.5 agents developed C-HD, a shortest-path algorithm with a Lean proof that achieves a better asymptotic upper bound than Dijkstra in a specific density regime.

  1. C-HD reduces repeated search work.

    The algorithm uses bounded local searches and maintains local invariants to limit processing even when revisiting vertices. It organizes recursive work using search trees and pivots.

    it reduces repeated search and data-structure work

  2. C-HD improves asymptotic bounds.

    Along the profile $m \approx n \log^{3/4} n$, C-HD achieves $O(n \log^{11/12} n)$, outperforming Dijkstra's $O(n \log n)$ as $n$ grows.

    I’ve achieved a better asymptotic upper bound as these graphs grow

  3. Large constants prevent practical speedups.

    While mathematically superior, the algorithm's formal construction contains enormous constants, meaning it may not perform faster on real-world graphs.

    this does not establish a practical speedup

  4. Agents compress problem-solving time.

    Ten Claude Opus 5.5 agents used a message board to collaborate, reorganize roles, and produce a reproducible Lean build in 15 hours.

    agents can dramatically compress the time it takes to make progress

Read the original ↗Save to your Sponge

Summarized with Sponge. Quotes are the author’s own words.

More from @bg

All readings →