This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Wang, I-L. Articles by Sokol, J. S. Search for Related Content

A Multiple Pairs Shortest Path Algorithm

Department of Industrial and Information Management, National Cheng Kung University, No. 1, University Road, Tainan, Taiwan 701
School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205
School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205
ilinwang{at}mail.ncku.edu.tw
ejohnson{at}isye.gatech.edu
jsokol{at}isye.gatech.edu

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.

Key Words: shortest path; multiple pairs; algebraic method; LU decomposition; Carré’s algorithm
History: Received: April 2004; revised: May 2005; accepted: May 2005.