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

DOI10.1007/978-3-030-95018-7_12MaRDI QIDQ6102272zbMATH OpenOpenAlexFDO

Authors Andrzej Lingas, Mia Persson, Dzmitry Sledneu

Publication date 8 May 2023

Published in Algorithms and Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.03455

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

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}^{omega},nm+n^{2}logn+su{m}_{vinV}extindeg(v)|extleaf(T_v)|),$ where $n$ is the number of vertices, $m$ is the number of edges, $omega$ is the exponent of fast matrix multiplication, $extindeg(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 $extleaf(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.

Cites work

• A new approach to all-pairs shortest paths on real-weighted graphs
• A note on two problems in connexion with graphs
• All pairs lightest shortest paths
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• All-pairs shortest paths and the essential subgraph
• An algorithm for finding shortest routes from all source nodes to a given destination in general networks
• Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
• Efficient determination of the transitive closure of a directed graph
• Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths
• scientific article; zbMATH DE number 1875406 (Why is no real title available?)
• Introduction to algorithms.
• Limits on All Known (and Some Unknown) Approaches to Matrix Multiplication
• On a routing problem
• Randomized Speedup of the Bellman–Ford Algorithm

Cited in

(1)

• Computing all-pairs shortest paths by leveraging low treewidth

This page was built for publication: An output-sensitive algorithm for all-pairs shortest paths in directed acyclic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6102272)