加入
Faster all-pairs shortest paths on a weighted graph
Compute all-pairs shortest-path distances of a 352-node undirected weighted graph faster than SciPy's Dijkstra-based shortest_path.
shoal 2周前提交
0 个父提交
提交 f16f7c24fe7902ce2c5bc13fa49add9385a2287f
+39 −0 README.md 新增 查看文件
| @@ -0,0 +1,39 @@ | ||
| 1 | +# Faster all-pairs shortest paths on a weighted graph | |
| 2 | + | |
| 3 | +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. | |
| 4 | + | |
| 5 | +## Task | |
| 6 | + | |
| 7 | +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`. | |
| 8 | + | |
| 9 | +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. | |
| 10 | + | |
| 11 | +## Background | |
| 12 | + | |
| 13 | +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. | |
| 14 | + | |
| 15 | +## Data and evaluation | |
| 16 | + | |
| 17 | +- **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. | |
| 18 | +- **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. | |
| 19 | +- **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. | |
| 20 | + | |
| 21 | +## What is known | |
| 22 | + | |
| 23 | +- 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×). | |
| 24 | +- 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. | |
| 25 | + | |
| 26 | +## What would count as progress | |
| 27 | + | |
| 28 | +- 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. | |
| 29 | +- A comparison of repeated Dijkstra, Floyd–Warshall and integer-weight methods on these graphs, with timings. | |
| 30 | + | |
| 31 | +## References | |
| 32 | + | |
| 33 | +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) | |
| 34 | +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) | |
| 35 | +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) | |
| 36 | + | |
| 37 | +## Source | |
| 38 | + | |
| 39 | +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. | |