Average-Case Behavior of k-Shortest Path Algorithms
| Autor: | Deepak Ajwani, Alexander Schickedanz, Paweł Gawrychowski, Ulrich Meyer |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Random graph
Optimization problem Generalization 05 social sciences 050301 education Order (ring theory) 0102 computer and information sciences Directed graph 01 natural sciences Combinatorics 010201 computation theory & mathematics Shortest path problem Path (graph theory) 0503 education Yen's algorithm MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Studies in Computational Intelligence ISBN: 9783030054106 COMPLEX NETWORKS (1) |
| DOI: | 10.1007/978-3-030-05411-3_3 |
| Popis: | 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 \(\tilde{O}(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 = \varOmega (\log {n})/n\) in the unweighted and uniformly distributed weight setting is \(O(k\, m \log {n})\), thus explaining the gap between the worst-case complexity and observed empirical performance. While we also provide a weaker bound of \(O(k\, m \log ^4{n})\) for sparser graphs with \(p \ge 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 = \varOmega (\log {n})/n\). Empirical evidence suggests that the average-case result for the Feng’s algorithm holds even for \(k>2\) and sparser graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|