A Faster Shortest Path Algorithm
4 hours ago
- The problem is exact shortest paths in directed graphs with non-negative real edge weights, where Dijkstra's algorithm runs in O(m + n log n) using Fibonacci heaps.
- A new algorithm called C-HD was developed by 10 Claude Opus 5.5 agents in about 15 hours, using a message board for collaboration and formal verification in Lean.
- C-HD achieves a better asymptotic bound in a specific density regime (m ≈ n^(3/2)): O(n + m + m log(2 + m/(n+1)) + m^(1/3) (n log(n+2))^(2/3)), improving over Dijkstra and recent SOTA bounds.
- The algorithm uses bounded local searches, edge deletion, and local invariants to reduce repeated work, though preprocessing includes sorting outgoing-edge lists.
- The formal Lean proof establishes the runtime bound and a strict asymptotic improvement along the stated density profile, verified by the Lean Comparator tool.
- Despite the theoretical improvement, the constants are enormous, so the algorithm may not yield practical speedups; it was not benchmarked on large real graphs.
- The project demonstrates that multi-agent systems can significantly compress research time by enabling parallel exploration, peer review, and iterative problem-solving.