Routing Faster Than Dijkstra Thanks to Contraction Hierarchies

Part 1

If path A →B is optimal, then path X1 →X2 is also optimal.
Optimal path X1 →X2 is not part of optimal path A →B if refueling is part of the problem
Example showing a shortest path problem, partially solved with Dijkstra. Solved nodes are in blue, next nodes to be solved are in green, while unexplored nodes are in red.
Computer generated map from a European navigation map database.
Dijkstra algorithm at work. Credit to Wikipedia.
Radius of the Dijkstra search area is typically proportional to the distance between the start and destination nodes (search area in red)
+-------------+--------------------+
| #links | #visited | Routing |
| in solution | nodes | time (s)|
+-------------+----------+---------+
| 10 | 491 | 0.005 |
| 100 | 14074 | 0.730 |
| 1000 | 1581057 | 4.861 |
+-------------+----------+---------+
An easy win by searching simultaneously from the start and destination nodes.
This picture illustrates a decomposition of the problem through several layers of different importance, as well as my ability to use Paint.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store