A multiple pairs shortest path algorithm

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

研究成果: Article同行評審

13 引文 斯高帕斯(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.

原文English
頁(從 - 到)465-476
頁數12
期刊Transportation Science
39
發行號4
DOIs
出版狀態Published - 2005 十一月

All Science Journal Classification (ASJC) codes

  • 土木與結構工程
  • 運輸

指紋

深入研究「A multiple pairs shortest path algorithm」主題。共同形成了獨特的指紋。

引用此