arXiv:2611.17215 · v1

Faster Deterministic All-Pairs Shortest Paths with Real Edge Weights

更快确定性的实权全源最短路径算法

首次提交 2026-11-13 02:13

版本更新 2026-11-13 02:13

雷达观测 2026-11-13 14:15

摘要

For directed $n$-vertex graphs with arbitrary finite real edge weights and no negative cycles, we compute all-pairs distances deterministically in $O(n^{2.9929729})$ worst-case time using Uznański's half-width matrix multiplication bound. Using only the Le Gall--Urrutia rectangular multiplication bounds, our algorithm runs in $O(n^{2.99306273})$ time. This improves both the deterministic bound of $O(n^{2.9997})$ due to Chan, Itakura, Ma and Yu and the Las Vegas expected-time bound of $O(n^{2.993805})$ reported in the shreshth-s working note.

作者备注：35 pages