# An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs

Preprint · Andrzej Lingas, Mia Persson, Dzmitry Sledneu

- Archive id: arxiv:2108.03455
- Published: 2021-08-07
- arXiv: https://arxiv.org/abs/2108.03455
- Citations: 0
- Source URL: https://arxiv.org/abs/2108.03455
- PDF: https://arxiv.org/pdf/2108.03455
- Provenance: arxiv

## Abstract

A straightforward dynamic programming method for the single-source shortest paths problem (SSSP) in an edge-weighted directed acyclic graph (DAG) processes the vertices in a topologically sorted order. First, we similarly iterate this method alternatively in a breadth-first search sorted order and the reverse order on an input directed graph with both positive and negative real edge weights, $n$ vertices and $m$ edges. For a positive integer $t,$ after $O(t)$ iterations in $O(tm)$ time, we obtain for each vertex $v$ a path distance from the source to $v$ not exceeding that yielded by the shortest path from the source to $v$ among the so called {\\em$ t+$light paths}. A directed path between two vertices is $t+$light if it contains at most $t$ more edges than the minimum edge-cardinality directed path between these vertices. After $O(n)$ iterations, we obtain an $O(nm)$-time solution to SSSP in directed graphs with real edge weights matching that of Bellman and Ford. Our main result is an output-sensitive algorithm for the all-pairs shortest paths problem (APSP) in DAGs with positive and negative real edge weights. It runs in time $O(\\min \\{n^ω, nm+n^2\\log n\\}+\\sum\_{v\\in V}\\text{indeg}(v)\|\\text{leaf}(T\_v)\|),$ where $n$ is the number of vertices, $m$ is the number of edges, $ω$ is the exponent of fast matrix multiplication, $\\text{indeg}(v)$ stands for the indegree of $v,$ $T\_v$ is a tree of lexicographically-first shortest directed paths from all ancestors of $v$ to $v$, and $\\text{leaf}(T\_v)$ is the set of leaves in $T\_v.$ Finally, we discuss an extension of hypothetical improved upper time-bounds for APSP in non-negatively edge-weighted DAGs to include directed graphs with a polynomial number of large directed cycles.

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