### An Experimental Study on Approximating $\textit{k}$ Shortest Simple PathsAn Experimental Study on Approximating $\textit{k}$ Shortest Simple Paths

Access Restriction
Subscribed

 Author Frieder, Asaf ♦ Roditty, Liam Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2015 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data Subject Keyword k shortest paths ♦ Heuristic ♦ Path approximation ♦ Second path Abstract We have conducted an extensive experimental study on approximation algorithms for computing $\textit{k}$ shortest simple paths in weighted directed graphs. Very recently, Bernstein [2010] presented an algorithm that computes a 1 + ϵ approximated $\textit{k}$ shortest simple path in $O(ϵ^{-1}k(m$ + $\textit{n}$ $\textit{log}$ $\textit{n})$ $log^{2}$ $\textit{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. ISSN 10846654 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2015-04-03 Publisher Place New York e-ISSN 10846654 Journal Journal of Experimental Algorithmics (JEA) Volume Number 19 Page Count 15 Starting Page 1 Ending Page 15

#### Open content in new tab

Source: ACM Digital Library