Speeding Up Dynamic Shortest-Path Algorithms

Speeding Up Dynamic Shortest-Path Algorithms

0.00 Avg rating0 Votes
Article ID: iaor200952607
Country: United States
Volume: 20
Issue: 2
Start Page Number: 191
End Page Number: 204
Publication Date: Mar 2008
Journal: INFORMS Journal On Computing
Authors: , ,
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.

Reviews

Required fields are marked *. Your email address will not be published.