Speeding Up Dynamic Shortest-Path Algorithms
Authors:
- 1 May 2008
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in INFORMS Journal on Computing
- Vol. 20 (2) , 191-204
Abstract
Dynamic shortest-path algorithms update the shortest paths taking into account a change in an arc weight. This paper describes a new generic technique that allows the reduction of heap sizes used by several dynamic single-destination shortest-path algorithms. For unit weight changes, the updates can be done without heaps. These reductions almost always reduce the computational times for these algorithms. In computational testing, several dynamic shortest-path algorithms with and without the heap-reduction technique are compared. Speedups of up to a factor of 1.8 were observed using the heap-reduction technique on random weight changes and of over a factor of five on unit weight changes. We compare as well with Dijkstra's algorithm, which recomputes the paths from scratch. With respect to Dijkstra's algorithm, speedups of up to five orders of magnitude are observed.Keywords
This publication has 16 references indexed in Scilit:
- A hybrid genetic algorithm for the weight setting problem in OSPF/IS‐IS routingNetworks, 2005
- Increasing Internet Capacity Using Local SearchComputational Optimization and Applications, 2004
- Fully Dynamic Algorithms for Maintaining Shortest Paths TreesJournal of Algorithms, 2000
- An Incremental Algorithm for a Generalization of the Shortest-Path ProblemJournal of Algorithms, 1996
- On the computational complexity of dynamic graph problemsTheoretical Computer Science, 1996
- Shortest paths algorithms: Theory and experimental evaluationMathematical Programming, 1996
- A note on the problem of updating shortest pathsNetworks, 1981
- An On-Line Edge-Deletion ProblemJournal of the ACM, 1981
- Reoptimization procedures in shortest path problemDecisions in Economics and Finance, 1980
- A new shortest path updating algorithmNetworks, 1978