Optimization Online


Speeding up dynamic shortest path algorithms

Luciana S. Buriol (buriol***at***densis.fee.unicamp.br)
Mauricio G.C. Resende (mgcr***at***research.att.com)
Mikkel Thorup (mthorup***at***research.att.com)

Abstract: Dynamic shortest path algorithms update the shortest paths to take into account a change in an edge weight. This paper describes a new technique that allows the reduction of heap sizes used by several dynamic shortest path algorithms. For unit weight change, 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: Shortest path algorithms, Dijkstra's algorithm, heaps, graphs, trees.

Category 1: Network Optimization

Citation: AT&T Labs Research Technical Report TD-5RJ8B. September 19, 2003.

Download: [PDF]

Entry Submitted: 09/19/2003
Entry Accepted: 09/22/2003
Entry Last Modified: 09/19/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society