Average-Case Behavior of k-Shortest Path Algorithms

Files in This Item:
Access to this item has been restricted by the copyright holder until:2019-12-02
File Description SizeFormat 
ajwani_complex_networks18.pdf559.17 kBAdobe PDFDownload    Request a copy
Title: Average-Case Behavior of k-Shortest Path Algorithms
Authors: Schickedanz, Alexander
Ajwani, Deepak
Meyer, Ulrich
Gawrychowski, Pawel
Permanent link: http://hdl.handle.net/10197/9887
Date: 2-Dec-2018
Online since: 2019-04-10T10:58:01Z
Abstract: The k-shortest path problem is a generalization of the fundamental shortest path problem, where the goal is to compute k simple paths from a given source to a target node, in non-decreasing order of their weight. With numerous applications modeling various optimization problems and as a feature in some learning systems, there is a need for efficient algorithms for this problem. Unfortunately, despite many decades of research, the best directed graph algorithm still has a worst-case asymptotic complexity of Õ(k n(n + m)). In contrast to the worst-case complexity, many algorithms have been shown to perform well on small diameter directed graphs in practice. In this paper, we prove that the average-case complexity of the popular Yen’s algorithm on directed random graphs with edge probability p = Ω(log n)/n in the unweighted and uniformly distributed weight setting is O(kmlog n), thus explaining the gap between the worst-case complexity and observed empirical performance. While we also provide a weaker bound of O(kmlog4 n) for sparser graphs with p ≥ 4/n, we show empirical evidence that the stronger bound should also hold in the sparser setting. We then prove that Feng’s directed k-shortest path algorithm computes the second shortest path in expected O(m) time on random graphs with edge probability p = Ω(log n)/n. Empirical evidence suggests that the average-case result for the Feng's algorithm holds even for k > 2 and sparser graphs.
Type of material: Conference Publication
Publisher: Springer
Volume: 812
Start page: 28
End page: 40
Series/Report no.: Studies in Computational Intelligence
Copyright (published version): 2019 Springer
Keywords: k-Shortest path algorithmsAverage case analysisYen’s algorithmFeng’s algorithm
DOI: 10.1007/978-3-030-05411-3_3
Other versions: https://www.2018.complexnetworks.org/
Language: en
Status of Item: Peer reviewed
Is part of: Studies in Computational Intelligence (SCI, volume 812)
Conference Details: The 7th International Conference on Complex Networks and Their Applications, Cambridge, United Kingdom, 11-13 December 2018
ISBN: 9783030054106
Appears in Collections:Computer Science Research Collection

Show full item record

Google ScholarTM

Check

Altmetric


This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. For other possible restrictions on use please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.