Routing Faster Than Dijkstra Thanks to Contraction Hierarchies

Part 1

Dijkstra and the wonderful world of 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

  • 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

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

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

  • 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).

--

--

--

Passionate software developer https://jsgonsette.github.io/

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

The future of testing

Web Dev Bytes — Happy with API’s

Why Kubernetes Has Become So Popular in Data Engineering

City view by the river

Set up a self-hosted video conference server (Jitsi)

Your legacy codebase isn’t a nightmare because of the code

Developer at Google Summer of Code ’18 with Inria Foundation (SOFA and Pulse)

Getting Excited about Events

Clusterstack 1.1.40 — The Last of the Mohicans

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
Jean-Sébastien Gonsette

Jean-Sébastien Gonsette

Passionate software developer https://jsgonsette.github.io/

More from Medium

50 Days of consistent coding with Scaler Community

Leetcode: Lowest Common Ancestor of a Binary Tree

Understanding Pair Programming, Why 2 Minds Are Greater Than 1.

An illustration showing how pair programming works in the workplace.

Learning to program was and is way more interesting.