Introduction

This is a cross-post from http://blog.tristramg.eu/short-history-of-routes-computation.html

I wrote a blog post in French that had some unexpected success (by success I mean that people actually read it). At least two people asked for an English translation. So here it goes, with some of the errors of the French version corrected.

Formally we would speak of “shortest path in a graph problem”. The goal is the same: what is the shortest way to go from A to B.

Route computation are nice as the actual use cases can be explained to anyone:

• the GPS end user
• the computer science student that at some point learnt the basic algorithms
• there is still research going on, but it can be explained to anyone interested within a few pints

Personally, what I find interesting is how those algorithms evolved through time. Sorry for punctual technical details.

Read the rest of this entry →