A multiple pairs shortest path algorithm

I. Lin Wang, Ellis L. Johnson, Joel S. Sokol

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)465-476
Number of pages12
JournalTransportation Science
Issue number4
Publication statusPublished - 2005 Nov

All Science Journal Classification (ASJC) codes

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'A multiple pairs shortest path algorithm'. Together they form a unique fingerprint.

Cite this