An Output-Sensitive Algorithm for All-Pairs Shortest Paths in Directed Acyclic Graphs
(2022) 8th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2022 In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 13179 LNCS. p.140-151- Abstract
First, we present a new algorithm for the single-source shortest paths problem (SSSP) in edge-weighted directed graphs, with n vertices, m edges, and both positive and negative real edge weights. Given a positive integer parameter t, in O(tm) time the algorithm finds 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 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. For t= O(n), our algorithm yields an O(nm)-time solution to SSSP in directed graphs with real edge weights matching that of Bellman and Ford. Our main... (More)
First, we present a new algorithm for the single-source shortest paths problem (SSSP) in edge-weighted directed graphs, with n vertices, m edges, and both positive and negative real edge weights. Given a positive integer parameter t, in O(tm) time the algorithm finds 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 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. For t= O(n), our algorithm yields an O(nm)-time solution to SSSP in directed graphs with real edge weights matching that of Bellman and Ford. Our main contribution is a new, output-sensitive algorithm for the all-pairs shortest paths problem (APSP) in directed acyclic graphs (DAGs) with positive and negative real edge weights. The running time of the algorithm depends on such parameters as the number of leaves in (lexicographically first) shortest-paths trees, and the in-degrees in the input graph. If the trees are sufficiently thin on the average, the algorithm is substantially faster than the best known algorithm. 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.
(Less)
- author
- Lingas, Andrzej LU ; Persson, Mia LU and Sledneu, Dzmitry
- organization
- publishing date
- 2022
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- Algorithms and Discrete Applied Mathematics - 8th International Conference, CALDAM 2022, Proceedings
- series title
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
- editor
- Balachandran, Niranjan and Inkulu, R.
- volume
- 13179 LNCS
- pages
- 12 pages
- publisher
- Springer Science and Business Media B.V.
- conference name
- 8th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2022
- conference location
- Puducherry, India
- conference dates
- 2022-02-10 - 2022-02-12
- external identifiers
-
- scopus:85124662790
- ISSN
- 0302-9743
- 1611-3349
- ISBN
- 9783030950170
- DOI
- 10.1007/978-3-030-95018-7_12
- language
- English
- LU publication?
- yes
- id
- d027e21d-0fcb-4d5e-8039-a203a305fe2c
- date added to LUP
- 2022-04-13 13:56:18
- date last changed
- 2024-06-18 16:02:11
@inproceedings{d027e21d-0fcb-4d5e-8039-a203a305fe2c,
abstract = {{<p>First, we present a new algorithm for the single-source shortest paths problem (SSSP) in edge-weighted directed graphs, with n vertices, m edges, and both positive and negative real edge weights. Given a positive integer parameter t, in O(tm) time the algorithm finds 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 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. For t= O(n), our algorithm yields an O(nm)-time solution to SSSP in directed graphs with real edge weights matching that of Bellman and Ford. Our main contribution is a new, output-sensitive algorithm for the all-pairs shortest paths problem (APSP) in directed acyclic graphs (DAGs) with positive and negative real edge weights. The running time of the algorithm depends on such parameters as the number of leaves in (lexicographically first) shortest-paths trees, and the in-degrees in the input graph. If the trees are sufficiently thin on the average, the algorithm is substantially faster than the best known algorithm. 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.</p>}},
author = {{Lingas, Andrzej and Persson, Mia and Sledneu, Dzmitry}},
booktitle = {{Algorithms and Discrete Applied Mathematics - 8th International Conference, CALDAM 2022, Proceedings}},
editor = {{Balachandran, Niranjan and Inkulu, R.}},
isbn = {{9783030950170}},
issn = {{0302-9743}},
language = {{eng}},
pages = {{140--151}},
publisher = {{Springer Science and Business Media B.V.}},
series = {{Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)}},
title = {{An Output-Sensitive Algorithm for All-Pairs Shortest Paths in Directed Acyclic Graphs}},
url = {{http://dx.doi.org/10.1007/978-3-030-95018-7_12}},
doi = {{10.1007/978-3-030-95018-7_12}},
volume = {{13179 LNCS}},
year = {{2022}},
}