the shortest way from Rotterdam to Groningen

in 1956, Edsger Dijkstra wanted to show what the new ARMAC computer could do, with a problem people outside computing would get. he picked this one: what's the shortest way to travel from Rotterdam to Groningen?

he worked it out on a café terrace in Amsterdam, having coffee with his fiancée. he called it "a twenty-minute invention", and said he designed it without pencil and paper.

I'm using a pencil anyway.

#fewer stops, more minutes

here's a small map. the roads are one-way, and the numbers are minutes.

breadth-first search finds the route with the fewest roads: home, A, work. that's 7 minutes. going through B adds a stop and takes 6.

breadth-first search counts roads. Dijkstra's algorithm counts minutes. every road has a weight, here the minutes it takes, and the shortest path is the one whose weights add up to the least.

#working it out by hand

keep a note of the quickest time you know to each place. then, over and over, take the cheapest place you haven't finished and check whether going through it gets you anywhere quicker.

1. from home, A is 6 and B is 2. no road goes from home to work, so work is infinity for now.
2. B is the cheapest. through B, A is 2 + 3 = 5, a minute less than going straight. work is 2 + 5 = 7. B is finished.
3. A is next, at 5. through A, work is 5 + 1 = 6. A is finished.
4. only work is left: 6 minutes, through B and A.

once a place is the cheapest one left, nothing can beat its time. any other way there goes through a place that already costs more, and roads only add minutes. the cheapest place left is final.

#in code

the graph is a hash table of hash tables: each place, the places it has roads to, and how long each one takes. two more keep the notes: costs, the quickest time found so far to each place, and parents, the place that time came through. a set holds the finished ones.

const graph = {
  home: { A: 6, B: 2 },
  A: { work: 1 },
  B: { A: 3, work: 5 },
  work: {},
};
 
const costs = { A: 6, B: 2, work: Infinity };
const parents = { A: 'home', B: 'home', work: null };
const finished = new Set();
 
function cheapest() {
  let lowest = Infinity;
  let found = null;
  for (const place in costs) {
    if (costs[place] < lowest && !finished.has(place)) {
      lowest = costs[place];
      found = place;
    }
  }
  return found;
}
 
let place = cheapest();
while (place !== null) {
  for (const [next, minutes] of Object.entries(graph[place])) {
    const through = costs[place] + minutes;
    if (through < costs[next]) {
      costs[next] = through;
      parents[next] = place;
    }
  }
  finished.add(place);
  place = cheapest();
}
 
const route = ['work'];
while (route[0] !== 'home') route.unshift(parents[route[0]]);
console.log(costs.work, route.join(' → ')); // 6 home → B → A → work

cheapest() looks at every place each time, which is fine for four of them. on a map with thousands, you'd keep them in a priority queue, so the next cheapest comes out without looking at all the others.

#where it breaks

a negative weight breaks it. say the road from B to A takes -4 minutes:

A is the cheapest at 2, so it's finished first, and work gets 3. then B, at 5, finds a way to A for 5 - 4 = 1. too late: A is finished and won't be picked again, so work stays at 3. the real quickest is home, B, A, work, in 2.

run the code above on this map and it prints 3 home → B → A → work: the right route with the wrong time.

the cheapest place left is only final when no road takes minutes away. for negative weights there's the Bellman-Ford algorithm. it's slower: it goes over every road once for each place on the map.

Dijkstra published it in 1959, in a paper three pages long. this post is longer, and I needed the pencil.