Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/11305
Title: k-Shortest path algorithms
Authors: Santos, José Luis 
Keywords: Shortest path; Ranking path; Deviation path
Issue Date: 2007
Publisher: Centro de Matemática da Universidade de Coimbra
Citation: Pré-Publicações DMUC. 07-07 (2007)
Abstract: This paper focuses on algorithms to solve the k-shortest path problem. Three codes are described and compared on random generated and real-world networks. One million paths were ranked in less than 3 seconds (3 microseconds per path), with at most 1 second of preprocessing, on random generated networks with 10 000 nodes. For real-world instances with more than one million nodes, the preprocessing time rises up to 2,7 hours and the CPU time to rank one million paths is less than 30 seconds (30 microseconds per path).
URI: http://hdl.handle.net/10316/11305
Rights: openAccess
Appears in Collections:FCTUC Matemática - Vários

Files in This Item:
File Description SizeFormat
k-Shortest path algorithms.pdf192.72 kBAdobe PDFView/Open
Show full item record

Page view(s)

119
checked on Dec 9, 2019

Download(s) 50

327
checked on Dec 9, 2019

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.