Name
Abstract | ||
|---|---|---|
We present significant improvements to a practical algorithm for the point-to-point shortest path problem on road networks that com- bines Asearch, landmark-based lower bounds, and reach-based pruning. Through reach-aware landmarks, better use of cache, and improved algo- rithms for reach computation, we make preprocessing and queries faster while reducing the overall space requirements. On the road networks of the USA or Europe, the shortest path between two random vertices can be found in about one millisecond after one or two hours of preprocessing. The algorithm is also effective on two-dimensional grids. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-72845-0_4 | Workshop on Experimental and Efficient Algorithms |
Keywords | Field | DocType |
overall space requirement,point-to-point shortest path problem,road network,better use,reach computation,shortest path,random vertex,practical algorithm,improved algorithm,lower bound,better landmark,shortest path problem,point to point | Canadian traveller problem,Shortest path problem,Algorithm,Distance,Constrained Shortest Path First,Yen's algorithm,Artificial intelligence,Shortest Path Faster Algorithm,Machine learning,Mathematics,Euclidean shortest path,K shortest path routing | Conference |
Volume | ISSN | Citations |
4525 | 0302-9743 | 36 |
PageRank | References | Authors |
2.50 | 32 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew V. Goldberg | 1 | 5883 | 676.30 |
| Haim Kaplan | 2 | 3581 | 263.96 |
| Renato F. Werneck | 3 | 1743 | 84.33 |