Faster all-pairs shortest paths on a weighted graph

Compute the shortest-path distance between every pair of nodes of an undirected weighted graph faster than SciPy's Dijkstra-based routine. All-pairs distances feed network analysis, routing tables and graph-based machine learning.

Task

Input: the compressed sparse row adjacency of an undirected graph on $n$ nodes with positive integer edge weights from 1 to 100, produced by the task's generator from a random sparse matrix of density 0.2 made symmetric; in the benchmark $n=352$. Output: the $n\times n$ matrix of shortest-path distances, with None for unreachable pairs. An output is accepted when it has a zero diagonal, is symmetric, has no negative entries, and matches the reference under NumPy's allclose with relative tolerance $10^{-5}$ and absolute tolerance $10^{-8}$ (unreachable pairs must match too). The reference solver is scipy.sparse.csgraph.shortest_path with method='D' (Dijkstra from every node) and directed=False.

Score: the reference's run time divided by the candidate's, averaged over the test instances; it is 1 if any output fails the check, and speed-ups below 1 count as 1. Higher is better.

Background

Dijkstra's algorithm (1959) finds shortest paths from one source in a graph with non-negative weights; running it from every node gives all-pairs distances, while Floyd–Warshall does the same with a triple loop. Which is faster depends on density and implementation, and small integer weights allow specialized priority queues, so this task rewards matching the algorithm to the input.

Data and evaluation

• Instances: 100 test and 100 development instances from the task's generator at $n=352$, in the AlgoTune dataset; the reference needs about 100 ms per instance on the authors' machine.
• Evaluation code: the AlgoTune harness (./algotune.sh evaluate in the repository), which runs the task's checker on every output.
• Hardware: speed-ups depend on the machine, so reference and candidate are timed in the same environment. The paper keeps the fastest of 10 timed runs per instance, each after a warm-up, on an AMD EPYC 9454 CPU with 14 GB of memory; agents had 8 cores, and compilation is not timed.

What is known

• Best on the AlgoTune leaderboard as of 2026-10-20: 4.95×, by the AlgoTuner agent driven by Gemini 3.1 Pro Preview, ahead of GPT-5.4 (3.29×) and Gemini 3 Pro Preview (2.54×).
• Press et al. (2025) describe most agent speed-ups as surface-level: better library calls, better library usage or low-level rewrites, for example with Numba.

What would count as progress

• A solver beating 4.95× on all 100 test instances under the AlgoTune harness, with its code; anyone can rerun the checker and the timing.
• A comparison of repeated Dijkstra, Floyd–Warshall and integer-weight methods on these graphs, with timings.

References

1. O. Press, B. Amos, H. Zhao, et al. AlgoTune: Can language models speed up general-purpose numerical programs? NeurIPS 2025. arXiv:2507.15887
2. E. W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik 1, 269–271 (1959). doi:10.1007/BF01386390
3. P. Virtanen et al. SciPy 1.0: fundamental algorithms for scientific computing in Python. Nature Methods 17, 261–272 (2020). doi:10.1038/s41592-019-0686-2

Source

Imported from AlgoTune task shortest_path_dijkstra, curated by Ori Press and the AlgoTune contributors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.