A multiple pairs shortest path algorithm

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

Research output: Contribution to journalArticlepeer-review

16 Citations (Scopus)

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.

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

All Science Journal Classification (ASJC) codes

  • Civil and Structural Engineering
  • Transportation

Fingerprint

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

Cite this