Routing Faster Than Dijkstra Thanks to Contraction Hierarchies

Part 1

Dijkstra and the wonderful world of dynamic programming

The Dijkstra algorithm is not only an efficient algorithm; it is possible to show that for a general weighted graph with non-negative weights, this is the best algorithm, from an asymptotic point of view. And to understand the reason for such a performance, it is useful to recall the close connection it has with dynamic programming.

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

Dijkstra in practice

Even though dynamic programming fits well with a recursive processing approach, it is not mandatory and it is not what Dijkstra’s algorithm does in practice. The idea consists rather of an exploratory and iterative approach of the different nodes of the graph, but guaranteeing that a node is only explored once at most. To do so, these nodes are classified into three categories:

  • the explored nodes {Ei}, and for which a shorter path has already been found;
  • the nodes at the border of the exploration territory {Fj}, and which will be treated according to a certain order of priority. We will come back on this soon;
  • the unexplored nodes {Ok}, among which is the destination node that we are still trying to reach.
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.

The problem of large maps

Except for special graph cases, we have the assurance that there is nothing more efficient than Dijkstra to find the shortest path in a weighted graph. This is an algorithm widely used to calculate the route in a navigation system, such as the one in your car or in your smartphone.

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.

A heuristic to the rescue

This picture illustrates a decomposition of the problem through several layers of different importance, as well as my ability to use Paint.

A not-so-perfect heuristic

Although effective, this heuristic unfortunately brings a problem which is difficult to get rid of completely. Dijkstra’s algorithm must indeed be modified in order to operate with a stack of N maps instead of just one, and it will have to constantly ask itself at which level it has to work. Should he go up in layers in order to progress faster to the destination, at the risk of missing solutions that do not exist at such level of detail? Or is it better to go down, instead, to focus on a potential solution? Because the problem of the upper layers, which exclude the majority of the road network, comes from the assumption that finding the best solution doesn’t require any deeper investigation. This is sometimes true when the search criterion is time and when there is no traffic, but this is not always necessarily the case.

What if you could have your cake and eat it too ?

The general idea of the heuristic presented above is a good idea to reduce the size of the graph to explore. Unfortunately it also increases the search procedure complexity and prevent to find the optimal solution. In addition, it is based on a fixed hierarchy that is not necessarily the best.

  • build an hierarchy of road levels to reduce the searching time;
  • to have a mathematical guarantee to find the optimal solution;
  • that this hierarchy can be customized on demand for any possible metric (short, fast, eco route, whatever).

--

--

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