# Computing All-Pairs Shortest Paths by Leveraging Low Treewidth

Preprint · Léon R. Planken, Mathijs M. de Weerdt, Roman P. J. van der Krogt

- Archive id: arxiv:1401.4609
- Published: 2014-01-18
- Venue: Journal Of Artificial Intelligence Research, Volume 43, pages 353-388, 2012
- DOI: https://doi.org/10.1613/jair.3509
- arXiv: https://arxiv.org/abs/1401.4609
- Source URL: https://arxiv.org/abs/1401.4609
- PDF: https://arxiv.org/pdf/1401.4609
- Provenance: arxiv

## Abstract

We present two new and efficient algorithms for computing all-pairs shortest paths. The algorithms operate on directed graphs with real (possibly negative) weights. They make use of directed path consistency along a vertex ordering d. Both algorithms run in O(n^2 w\_d) time, where w\_d is the graph width induced by this vertex ordering. For graphs of constant treewidth, this yields O(n^2) time, which is optimal. On chordal graphs, the algorithms run in O(nm) time. In addition, we present a variant that exploits graph separators to arrive at a run time of O(n w\_d^2 + n^2 s\_d) on general graphs, where s\_d andlt= w\_d is the size of the largest minimal separator induced by the vertex ordering d. We show empirically that on both constructed and realistic benchmarks, in many cases the algorithms outperform Floyd-Warshalls as well as Johnsons algorithm, which represent the current state of the art with a run time of O(n^3) and O(nm + n^2 log n), respectively. Our algorithms can be used for spatial and temporal reasoning, such as for the Simple Temporal Problem, which underlines their relevance to the planning and scheduling community.

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

---
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.