More Web Proxy on the site http://driver.im/

research-article

An Experimental Study on Approximating k Shortest Simple Paths

Authors:

Liam RodittyAuthors Info & Claims

Journal of Experimental Algorithmics (JEA), Volume 19

Article No.: 1.5, Pages 1 - 15

https://doi.org/10.1145/2630068

Published: 03 April 2015 Publication History

Abstract

We have conducted an extensive experimental study on approximation algorithms for computing k shortest simple paths in weighted directed graphs. Very recently, Bernstein [2010] presented an algorithm that computes a 1 + ε approximated k shortest simple path in O(ε^-1k(m + n log n) log² n) time. We have implemented Bernstein’s algorithm and tested it on synthetic inputs and real-world graphs (road maps). Our results reveal that Bernstein’s algorithm has a practical value in many scenarios. Moreover, it produces in most of the cases exact paths rather than approximated. We also present a new variant for Bernstein’s algorithm. We prove that our new variant has the same upper bounds for the running time and approximation as Bernstein’s original algorithm. We have implemented and tested this variant as well. Our testing shows that this variant, which is based on a simple theoretical observation, is better than Bernstein’s algorithm in practice.

References

[1]

D. Aingworth, C. Chekuri, P. Indyk, and R. Motwani. 1999. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM J. Comput. 28, 4 (1999), 1167--1181.

Digital Library

[2]

A. Bernstein. 2010. A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs. In Proc. of 21st SODA. 742--755.

Digital Library

[3]

A. W. Brander and M. C. Sinclair. 1995. A comparative study of k-shortest path algorithms. In Proc. 11th UK Performance Engineering Workshop for Computer and Telecommunications Systems.

[4]

C. Demetrescu, M. Thorup, R. Chowdhury, and V. Ramachandran. 2008. Oracles for distances avoiding a failed node or link. SIAM J. Comput. 37, 5 (2008), 1299--1318.

Digital Library

[5]

D. Dor, S. Halperin, and U. Zwick. 2000. All-pairs almost shortest paths. SIAM J. Comput. 29, 5 (2000), 1740--1759.

Digital Library

[6]

D. Eppstein. 1998. Finding the k shortest paths. SIAM J. Comput. 28, 2 (1998), 652--673.

Digital Library

[7]

Z. Gotthilf and M. Lewenstein. 2009. Improved algorithms for the k simple shortest paths and the replacement paths problems. Inf. Process. Lett. 109, 7 (2009), 352--355.

Digital Library

[8]

E. Hadjiconstantinou and N. Christofides. 1999. An efficient implementation of an algorithm for finding k shortest simple paths. Networks 34, 2 (September 1999), 88--101.

[9]

V. Hatzivassiloglou and K. Knight. 1995. Unification-based glossing. Artif. Intell. (1995), 1382--1389.

Digital Library

[10]

J. Hershberger, M. Maxel, and S. Suri. 2007. Finding the k shortest simple paths: A new algorithm and its implementation. ACM Trans. Algorithms 3 (2007), 45.

Digital Library

[11]

J. Hershberger and S. Suri. 2001. Vickrey prices and shortest paths: What is an edge worth&quest; In Proc. of 42nd FOCS. 252--259.

Digital Library

[12]

N. Katoh, T. Ibaraki, and H. Mine. 1982. An efficient algorithm for k shortest simple paths. Networks 12, 4 (1982), 411--427.

[13]

E. L. Lawler. 1971/1972. A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Manage. Sci. 18 (1971/72), 401--405.

[14]

E. Martins, M. Pascoal, and J. Esteves dos Santos. 1999. Deviation algorithms for ranking shortest paths. Int. J. Found. Comp. Sci. 10, 3 (1999), 247--263.

[15]

A. Perko. 1986. Implementation of algorithms for k shortest loopless paths. Networks 16 (1986), 149--160.

[16]

L. Roditty. 2010. On the k shortest simple paths problem in weighted directed graphs. In SIAM J. Comput. 2363--2376.

Digital Library

[17]

L. Roditty and U. Zwick. 2005. Replacement paths and simple shortest paths in unweighted directed graphs. In Proc. of 32nd ICALP. 249--260.

Digital Library

[18]

V. Vassilevska Williams. 2011. Faster replacement paths. In Proc. of 22th SODA.

Digital Library

[19]

V. Vassilevska Williams and R. Williams. 2010. Subcubic equivalences between path, matrix and triangle problems. In Proc. FOCS.

Digital Library

[20]

J. Y. Yen. 1970/71. Finding the k shortest loopless paths in a network. Manage. Sci. 17 (1970/71), 712--716.

[21]

U. Zwick. 2002. All pairs shortest paths using bridging sets and rectangular matrix multiplication. JACM 49, 3 (2002), 289--317.

Digital Library

Cited By

Zhou BYe TNie YYu WWu C(2023)Generating Routes Less Fragile to Improve Disruption-Resilient Transport Protocol for Phasor Data in Optical IoT Networks of Power Transmission Grids2023 IEEE 29th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS60453.2023.00133(892-899)Online publication date: 17-Dec-2023
https://doi.org/10.1109/ICPADS60453.2023.00133
Zhou BYang QWang YWu C(2019)Reliable Communication in Transmission Grids based on Nondisjoint Path Aggregation Using Software-Defined NetworkingIEEE Transactions on Industrial Informatics10.1109/TII.2018.282812715:2(842-855)Online publication date: Feb-2019
https://doi.org/10.1109/TII.2018.2828127
Ajwani DDuriakova EHurley NMeyer USchickedanz A(2018)An Empirical Comparison of k-Shortest Simple Path Algorithms on MulticoresProceedings of the 47th International Conference on Parallel Processing10.1145/3225058.3225075(1-12)Online publication date: 13-Aug-2018
https://dl.acm.org/doi/10.1145/3225058.3225075
Show More Cited By

Index Terms

An Experimental Study on Approximating k Shortest Simple Paths
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation
  1. Design and analysis of algorithms
    1. Algorithm design techniques
      1. Dynamic programming

Recommendations

Replacement paths and k simple shortest paths in unweighted directed graphs

Let G = (V,E) be a directed graph and let P be a shortest path from s to t in G. In the replacement paths problem, we are required to find, for every edge e on P, a shortest path from s to t in G that avoids e. The only known algorithm for solving the ...
Finding the K shortest paths in a time-schedule network with constraints on arcs

We study a new variant of the time-constrained shortest path problem (TCSPP), that is, the K shortest paths problem in a time-schedule network with constraints on arcs. In such networks, each arc has a list of pre-specified departure times, and ...
Finding k shortest simple paths in directed graphs: A node classification algorithm

We propose a new exact algorithm for enumerating k shortest simple paths in a directed graph with n nodes and m edges. The algorithm has a complexity of Oknm+nlogn and follows the same process as Yen's deviation algorithm, but the candidate paths are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Journal of Experimental Algorithmics

ACM Journal of Experimental Algorithmics Volume 19, Issue

2014

402 pages

ISSN:1084-6654

EISSN:1084-6654

DOI:10.1145/2627368

Issue’s Table of Contents

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 April 2015

Accepted: 01 May 2014

Revised: 01 February 2014

Received: 01 March 2012

Published in JEA Volume 19

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
222
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou BYe TNie YYu WWu C(2023)Generating Routes Less Fragile to Improve Disruption-Resilient Transport Protocol for Phasor Data in Optical IoT Networks of Power Transmission Grids2023 IEEE 29th International Conference on Parallel and Distributed Systems (ICPADS)10.1109/ICPADS60453.2023.00133(892-899)Online publication date: 17-Dec-2023
https://doi.org/10.1109/ICPADS60453.2023.00133
Zhou BYang QWang YWu C(2019)Reliable Communication in Transmission Grids based on Nondisjoint Path Aggregation Using Software-Defined NetworkingIEEE Transactions on Industrial Informatics10.1109/TII.2018.282812715:2(842-855)Online publication date: Feb-2019
https://doi.org/10.1109/TII.2018.2828127
Ajwani DDuriakova EHurley NMeyer USchickedanz A(2018)An Empirical Comparison of k-Shortest Simple Path Algorithms on MulticoresProceedings of the 47th International Conference on Parallel Processing10.1145/3225058.3225075(1-12)Online publication date: 13-Aug-2018
https://dl.acm.org/doi/10.1145/3225058.3225075
Schickedanz AAjwani DMeyer UGawrychowski P(2018)Average-Case Behavior of k-Shortest Path AlgorithmsComplex Networks and Their Applications VII10.1007/978-3-030-05411-3_3(28-40)Online publication date: 2-Dec-2018
https://doi.org/10.1007/978-3-030-05411-3_3
Dalkılıç FDoğan YBirant DKut RYılmaz R(2017)A Gradual Approach for Multimodel Journey Planning: A Case Study in Izmir, TurkeyJournal of Advanced Transportation10.1155/2017/56563232017(1-14)Online publication date: 2017
https://doi.org/10.1155/2017/5656323

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents