# 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](https://huggingface.co/datasets/oripress/AlgoTune); the reference needs about 100 ms per instance on the authors' machine.
- **Evaluation code:** the AlgoTune harness (`./algotune.sh evaluate` in the [repository](https://github.com/oripress/AlgoTune)), 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](https://algotune.io) 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](https://arxiv.org/abs/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](https://doi.org/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](https://doi.org/10.1038/s41592-019-0686-2)

## Source

Imported from [AlgoTune task shortest_path_dijkstra](https://github.com/oripress/AlgoTune/tree/main/AlgoTuneTasks/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.