A bidirectional shortest-path algorithm with good average-case behavior |
| |
Authors: | Michael Luby Prabhakar Ragde |
| |
Affiliation: | 1. Department of Computer Science, University of Toronto, M5S 1A4, Toronto, Canada
|
| |
Abstract: | The two-terminal shortest-path problem asks for the shortest directed path from a specified nodes to a specified noded in a complete directed graphG onn nodes, where each edge has a nonnegative length. We show that if the length of each edge is chosen independently from the exponential distribution, and adjacency lists at each node are sorted by length, then a priority-queue implementation of Dijkstra's unidirectional search algorithm has the expected running time Θ(n logn). We present a bidirectional search algorithm that has expected running time Θ(√n logn). These results are generalized to apply to a wide class of edge-length distributions, and to sparse graphs. If adjacency lists are not sorted, bidirectional search has the expected running time Θ(a√n) on graphs of average degreea, as compared with Θ(an) for unidirectional search. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|