# the shortest way from Rotterdam to Groningen

2024-05-05 · 5 min read · #algorithms · #graphs

Source: https://jopcmelo.com/writing/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](https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#History) "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.

*(sketch: a map with four places: home, A, B and work. home to A takes 6 minutes, home to B 2, B to A 3, A to work 1 and B to work 5. the quickest route, home, B, A, work, is marked over it in dashes: 6 minutes, and a marker keeps taking it)*

[breadth-first search](/writing/introduction-to-graphs) 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.

*(sketch: handwritten notes of minutes from home: A's 6 crossed out for 5, B at 2, work's infinity crossed out for 7, then 7 crossed out for 6 and circled)*

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.

```javascript
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:

*(sketch: home to A takes 2 minutes, home to B 5, B to A minus 4 and A to work 1. A is finished first, the minus 4 road comes too late, and the algorithm says 3 minutes to work when it's really 2)*

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](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_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](https://doi.org/10.1007/BF01386390). this post is longer, and I needed the pencil.