Supercharged Dijkstra’s: Computing ‘shortest’ paths on large road...
summary
Claims a working Contraction Hierarchies implementation in Rust that answers shortest‑path queries on real road graphs (≈300,000 nodes, 800,000 edges). Empirical result: plain bidirectional Dijkstra averages ~13 ms per randomized query, the CH pipeline drops that to about 43 μs (sometimes ~60 μs), an order‑of‑magnitude speedup. The demo runs many randomized queries, measures latency, and shows added shortcuts during preprocessing that make queries dramatically faster.
AI-written summary · about
chapters (10)
- 0:00Shortest path algorithms intro
- 1:17Large road graphs challenge
- 2:00Dijkstra’s algorithm explained
- 3:50Bidirectional search optimization
- 4:32Benchmarking Dijkstra’s
- 5:14Contraction hierarchies intro
- 7:01How contraction hierarchies work
- 8:50Key considerations
- 9:11Performance results
- 10:17Summary
related talks
01h 01mDungeons, Dragons, and Graph Databases
32mGraph Databases, and Dungeons and Dragons
55mLet Me Graph That For You
31mDungeons, Dragons, and Graph Databases
38mNeo4j for Solving Graph-Based Problems
52mDungeons, Dragons, and Graph Databases
27mSpeed and Precision: Mastering Graph Traversal With Quantified Path Patterns
22mFishing for routes: exploring an application of pgRouting