.png){kind=icon}
返回
A multiple pairs shortest path algorithm
.png){kind=icon}
PRE
AI
DOI：10.1287/trsc.1050.0124.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
shortest path
multiple pairs
algebraic method
LU decomposition
Carres algorithm
期刊
IF:
4.8
论文数:
1.9K
被引数:
8.4K
机构
暂无机构信息
引用论文
.png){kind=icon}
Kinetic measurement of guanine deaminase in serum with a centrifugal analyzer.使用离心分析仪对血清中鸟嘌呤脱氨酶进行动力学测量。
OAAI
OAAI分享收藏
查看更多内容