A Multiple Pairs Shortest Path Algorithm

I-Lin Wang (), Ellis L. Johnson () and Joel S. Sokol ()
Additional contact information
I-Lin Wang: Department of Industrial and Information Management, National Cheng Kung University, No. 1, University Road, Tainan, Taiwan 701
Ellis L. Johnson: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205
Joel S. Sokol: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205

Transportation Science, 2005, vol. 39, issue 4, 465-476

Abstract: The multiple pairs shortest path problem (MPSP) arises in many applications where the shortest paths and distances between only some specific pairs of origin-destination (OD) nodes in a network are desired. The traditional repeated single-source shortest path (SSSP) and all pairs shortest paths (APSP) algorithms often do unnecessary computation to solve the MPSP problem. We propose a new shortest path algorithm to save computational work when solving the MPSP problem. Our method is especially suitable for applications with fixed network topology but changeable arc lengths and desired OD pairs. Preliminary computational experiments demonstrate our algorithm’s superiority on airline network problems over other APSP and SSSP algorithms.

Keywords: shortest path; multiple pairs; algebraic method; LU decomposition; Carré’s algorithm (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1050.0124 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:39:y:2005:i:4:p:465-476

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().