Average-Case Behavior of k-Shortest Path Algorithms
Files in This Item:
|ajwani_complex_networks18.pdf||559.17 kB||Adobe PDF||Download Request a copy|
|Title:||Average-Case Behavior of k-Shortest Path Algorithms||Authors:||Schickedanz, Alexander
|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 algorithms; Average case analysis; Yen’s algorithm; Feng’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
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.