Road Network Shortest-Path Acceleration Benchmark

What this research found

Route planning needs exact point-to-point shortest paths fast enough for interactive use, which a plain run of Dijkstra's algorithm cannot deliver on large road graphs. A heap-based Dijkstra baseline and an ALT-accelerated A-star search — goal-directed search steered by precomputed landmark distances and the triangle inequality — were implemented from scratch, with no external routing library, and compared on the DIMACS New York and Florida travel-time networks. Across 2,000 seeded random queries the accelerated search returned distances identical to Dijkstra every single time, while exploring 30.5 and 37.6 times fewer nodes on average and finishing the workload 2.58 and 2.11 times faster.

• Exactness held everywhere. The accelerated search matched Dijkstra's distance on all 1,000 sampled source–target pairs for each network, 2,000 of 2,000 with zero mismatches, empirically confirming that the landmark lower bound is admissible and that goal-directed pruning preserves optimality.
• The explored search space shrank by more than an order of magnitude. On New York the median settled-node count fell from 130,525.5 — roughly half the entire graph — to 6,424.0, and on Florida from 527,724.5 to 28,455.5, giving mean-per-query reductions of 30.54 times and 37.55 times.
• Realized time savings were smaller but consistent across the whole workload. New York's median query dropped from 262.3 ms to 71.1 ms and Florida's from 1,026.5 ms to 327.0 ms, for total-workload speedups of 2.58 times and 2.11 times, with the accelerated curve left of the baseline across essentially the entire distribution.
• The gap between a 30-to-38-times node reduction and a 2.1-to-2.6-times time speedup follows directly from the cost model. With 16 landmarks each node expansion performs up to 32 table lookups and comparisons, so the technique trades a per-node constant roughly an order of magnitude larger for an order-of-magnitude smaller node count.
• Preprocessing took 187.6 seconds for New York and 716.3 seconds for Florida, a 3.8-times increase for a 4.0-times larger node count, while the landmark tables grew exactly linearly from 64.5 MB to 261.3 MB. Notably the node-count speedup improved on the larger network (30.5 to 37.6 times) even as the wall-clock speedup edged down.

How it was done

Both networks came from the 9th DIMACS Implementation Challenge on Shortest Paths — New York with 264,346 nodes and 733,846 arcs, Florida with 1,070,376 nodes and 2,712,798 arcs, both on the travel-time metric — and were validated against the published header counts. Arcs were loaded into a shared compressed-sparse-row layout in both forward and backward form, so that any measured timing difference is attributable to the algorithm rather than the data structure. Preprocessing placed 16 landmarks by the farthest-point heuristic and ran 32 single-source Dijkstra searches to fill two dense landmark-by-node distance tables; at query time the heuristic takes the maximum, over both directions and all landmarks, of the triangle-inequality bound, which is admissible and so leaves the search exact. The benchmark then drew 1,000 random source–target pairs per network from a fixed seed, ran both algorithms on every pair, and recorded the returned distance, the wall-clock time and the settled-node count, reporting the minimum, median, mean, 95th percentile and maximum of each.

Data sources

• DIMACS 9th Implementation Challenge (Shortest Paths) — New York travel-time network, 264,346 nodes and 733,846 arcs
• DIMACS 9th Implementation Challenge (Shortest Paths) — Florida travel-time network, 1,070,376 nodes and 2,712,798 arcs
• Goldberg & Harrelson, SODA 2005 — the ALT landmark technique
• Bast et al., Algorithm Engineering: Selected Results and Surveys (2016) — route planning survey
• Dijkstra, Numerische Mathematik 1:269 (1959)