# Speeding up shortest path algorithms

Preprint · Andrej Brodnik, Marko Grgurovič

- Archive id: arxiv:1212.6327
- Published: 2012-12-27
- arXiv: https://arxiv.org/abs/1212.6327
- Citations: 0
- Source URL: https://arxiv.org/abs/1212.6327
- PDF: https://arxiv.org/pdf/1212.6327
- Provenance: arxiv

## Abstract

Given an arbitrary, non-negatively weighted, directed graph $G=(V,E)$ we present an algorithm that computes all pairs shortest paths in time $\\mathcal{O}(m^\* n + m \\lg n + nT\_ψ(m^\*, n))$, where $m^\*$ is the number of different edges contained in shortest paths and $T\_ψ(m^\*, n)$ is a running time of an algorithm to solve a single-source shortest path problem (SSSP). This is a substantial improvement over a trivial $n$ times application of $ψ$ that runs in $\\mathcal{O}(nT\_ψ(m,n))$. In our algorithm we use $ψ$ as a black box and hence any improvement on $ψ$ results also in improvement of our algorithm. Furthermore, a combination of our method, Johnson's reweighting technique and topological sorting results in an $\\mathcal{O}(m^\*n + m \\lg n)$ all-pairs shortest path algorithm for arbitrarily-weighted directed acyclic graphs. In addition, we also point out a connection between the complexity of a certain sorting problem defined on shortest paths and SSSP.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.