Solving k-shortest and constrained shortest path problems efficiently

Solving k-shortest and constrained shortest path problems efficiently

0.00 Avg rating0 Votes
Article ID: iaor1989309
Country: Switzerland
Volume: 20
Start Page Number: 249
End Page Number: 282
Publication Date: Aug 1989
Journal: Annals of Operations Research
Authors: ,
Keywords: networks: path
Abstract:

In this paper, the authors examine the problems of finding the k-shortest paths, the k-shortest paths without repeated nodes, and the shortest path with a single side constraint between an origin and destination pair. Distances are assumed to be non-negative, but networks may be either directed or undirected. Two versions of algorithms for all these problems are compared. The computational results show that, in each case, the advantage of the adaptive version (as measured by total number of permanent labels) grows with the problem size.

Reviews

Required fields are marked *. Your email address will not be published.