What is it about?
In practice, we usually need to know shortest paths between multiple pairs of origins and destinations, which is called as a Multiple Pairs Shortest Path problem (MPSP). Here we give a new MPSP algorithm, arguably more efficient than Dijkstra's algorithm and Floyd-Warshall algorithm, especially for cases with fixed topology and OD pairs but changeable arc lengths. Our algorithm is based on LU decomposition. We use a graphical way to implement an algebraic algorithm. Although the complexity is not as efficient as Dijkstra's algorithm in worst case, it is possible to save some time by sparse matrix techniques. Our algorithm can directly calculate a shortest path for a given OD pair.
Featured Image
Why is it important?
In telecommunication or transportation networks, often times the network topology (i.e., arcs and nodes) are fixed but arc lengths may change over time. Whenever arc lengths change, shortest paths between a certain set of OD pairs may change. If you use Dijkstra's algorithm, it is ok but it DOES NOT take advantage of the fixed topology. In addition, using a 1-ALL Dijkstra's algorithm is often an OVER KILL, especially if you only need to calculate few destinations but not ALL the n-1 destinations. Therefore, our algorithm called DLU may have good performance in such cases.
Perspectives
Our algorithm is an algebraic algorithm, and requires O(n^3) in the first LU decomposition phase. It is not suitable for large-scale networks. Also, if you do not use any sparse matrix techniques, your implementation may not perform well. It is more suitable for dense networks and better use sparse matrix techniques (or graphical implementation).
Professor I-Lin Wang
National Cheng Kuing University
Read the Original
This page is a summary of: A Multiple Pairs Shortest Path Algorithm, Transportation Science, November 2005, INFORMS,
DOI: 10.1287/trsc.1050.0124.
You can read the full text:
Contributors
The following have contributed to this page
