.png){kind=icon}
Return
A multiple pairs shortest path algorithm
.png){kind=icon}
PRE
AI
DOI：10.1287/trsc.1050.0124.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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
Carres algorithm
Journal
IF:
4.8
Papers:
1.9K
Citations:
8.4K
Organization
No organization information available
Cited Papers
.png){kind=icon}
ShareSaveShareSave
View more