Reusable Output-Sensitive Parallel Shortest-Path Searches

For a fixed directed graph with nonnegative real edge weights, polynomially many edges, and maximum total degree Delta = O(m/n), this paper gives a reusable version of the layered near-list hierarchy of Hair, Li, Li, and Zhang. After m^(1+o(1)) + n^(1+o(1)) t^2 shared preprocessing work and n^(1+o(1))/t span, an exact distance-ball query returning q vertices uses n^o(1)((q+1)t^2 + Delta q) work and n^o(1)(q/t + 1) span on a deterministic CREW arithmetic PRAM. Queries return exact distances and a shortest-path predecessor tree. The extension is a branch-relative rebuild schedule with fresh slack at temporary branches and rounded-volume accounting. The paper specifies persistent parallel state, eager boundary keys, exact buffer ordering, and final-partial-buffer accounting. Polynomially many independent queries can share immutable preprocessing. The graph and weights remain fixed, and the result does not assert a rational input-bit bound or a negative-weight shortest-path algorithm. Disclosure of AI assistance. OpenAI Codex assisted with literature searches, development and checking of the mathematical arguments, numerical sanity checks, manuscript organization, and preparation of the LaTeX source. The author is responsible for the claims, proofs, citations, and final presentation. The work has not been formally verified, and this disclosure does not assert external peer review.