// HACKER NEWS — CYBERSECURITY
A Faster Shortest Path Algorithm
Shortest paths is a very simple problem. There is a graph of vertices and (possibly directed) edges that connect them. Each edge has a real number weight. Starting from some vertex, for every other vertex in the graph you want to find the minimum total weight of a path, or report that it is unreachable.
In the version I considered, the graph was directed, I required exact answers and was given non-negative real weights for the edges.
I assume that real number weights can be compared and added. Any operations the shortest path algorithm does internally (such as counting how many nodes are visited or storing distances on intermediate vertices) counts towards running time.
With this setup, the classic Dijkstra’s shortest path algorithm runs in O(m+nlogn)O(m+n\log n)O(m+nlogn) time, where n≥2n \ge 2n≥2 is the number of vertices and mmm is the number of edges in the input graph. This is achieved using a suitable priority queue data structure, such as a Fibonacci heap. For m≥nm\ge nm≥n, other deterministic algorithms achieve O(mlog2/3n)O(m \log^{2/3} n)O(mlog2/3n), first introduced in this 2025 breakthrough paper, and O(mlogn+mnlognloglogn)O(m \sqrt{\log n} + \sqrt{mn \log n \log\log{n}})O(mlogn+mnlognloglogn) (this 2026 follow up).
Given these bounds, there’s a broad area of the parameter space for mmm as a function of nnn where Dijkstra is better. So I invited my agents to figure out what’s possible if the weights were non-negative reals, and to prove correctness and efficiency using Lean, the formal verification tool.
After about 15 hours and 733 messages on the message board, the team had completed a proposed new algorithm for finding exact shortest-path distances in the directed graph setting. This algorithm, called C-HD, is presented in this Lean proof.
The algorithm handles local search which encounter unproductive edges quite well. It still uses priority comparisons, but a newly encountered vertex can count towards a search’s size limit as an unexplored leaf. The algorithm maintains local invariants (rules that stay true after each update), with careful edge deletion and a bounded local search. This enables it to achieve this bound within its certified range:
where n≥2n \ge 2n≥2 is the number of vertices in the input graph and mmm is the number of edges. The certified range is m≤n⌊⌊log2n⌋3/4⌋m\le n\lfloor\lfloor\log_2 n\rfloor^{3/4}\rfloorm≤n⌊⌊log2n⌋3/4⌋. For this analysis, I also add overhead of allocating memory, sorting edges, reading the input graph, and outputting results.
An intuitive explanation of why C-HD has a better bound than Dijkstra or the listed SOTA algorithms in the relevant regime is that it reduces repeated search and data-structure work. The idea is:
This deterministic procedure limits repeated work. The algorithm C-HD implements carefully handles local invariants so that even if it revisits the same endpoint/vertex a few times, repeated processing can be bounded. In this way, C-HD achieves a better bound on total work in the stated regime, even though it doesn’t know the order of visiting vertices beforehand. It still reads the entire input graph.