!!COn 2020 - Supercharged Dijkstra’s: Computing ‘shortest’ paths on large road... by Payas Rajan
4Supercharged Dijkstra’s: Computing ‘shortest’ paths on large road graphs in microseconds! by Payas Rajan
Road networks are often modeled as graphs with millions of edges, and finding a ‘shortest’ path on them is a fundamental operation for several applications. When Fibonacci heaps are used, Dijkstra’s algorithm provides an asymptotically optimal solution to the shortest path problem. However, in practice, Dijkstra’s is too slow for unaltered use in mapping services. In this talk, I shall present Contraction Hierarchies, a technique that can speed up the shortest path computation by almost an order of magnitude or more!
Payas once wanted to study History, but is now working towards a PhD in Computer Science at the University of California - Riverside. His research involves developing strange versions of route planning algorithms for transportation networks, and sometimes, more broadly, algorithm engineering. He used to work for Samsung Research.