Routes: Edsger Dijkstra

12 March 2018

In a 2001 interview with Philip L Frana for the Charles Babbage Institute, Edsger Dijkstra succinctly demonstrated the importance of his shortest path algorithm:

Dijkstra: If, these days, you want to go from here to there and you have a car with a GPS and a screen, it can give you the shortest way from your hotel to Robbie Creek Cove. Yes?
Frana: I did generate a map, yes, on line.
Dijkstra: Did you use it?
Frana: Yes, I did use it.
Dijkstra: Then you used my algorithm this morning.

The roots of mathematics reach back through time for centuries, providing a solid foundation by anchoring our knowledge in the ages of Pythagoras, Euclid, Fibonacci, Galileo, and Newton. However, some areas of mathematics are new. Their roots are not deep, yet they still carry the huge weight of technological advances that we use, and take for granted, every day.

Edsger Wybe Dijkstra was born in Rotterdam, the Netherlands, in 1930. Dijkstra’s father, Douwe, taught chemistry at a local secondary school, whilst his mother, Brechtje, was a trained mathematician.

Edsger W Dijkstra (Source: Hamilton Richards, CC BY-SA 3.0)

When describing his mother, Dijkstra states: “she had a great agility in manipulating formulae and a wonderful gift for finding very elegant solutions”. This elegance permeates his own work and is evident throughout his writings. Dijkstra’s catalogue of carefully numbered manuscripts, known as EWDs, which document his ideas, reports, lectures, proofs, and letters, are fascinating to read. Dijkstra wrote a great deal of them by hand, in fountain pen. Most of them can be found at the archive hosted by the University of Texas where he worked from 1984 until his retirement.

As a teenager, Dijkstra had career aspirations to represent his country—he believed that he could study for a degree in law and follow this path in order to serve on the United Nations council—however, following outstanding results in maths and the sciences, Dijkstra was persuaded to enrol at the University of Leiden in 1948 to study maths and physics.

It was the result of what Dijkstra called “a long series of coincidences” that led to him becoming the Netherlands’ first programmer in 1952. In The Humble Programmer, his acceptance speech when receiving the Turing Award in 1972, Dijkstra tells how his father enrolled him on a short programming course at the University of Cambridge in 1951. It was felt that this course would help Dijkstra in the long term as a theoretical physicist. The head of the Amsterdam Mathematical Centre heard that a fellow Dutch citizen had taken the programming course, and in light of the fact that the centre was building computers, offered Dijkstra a job. Dijkstra was convinced that programming could become a respectable discipline, and so finished his physics studies in Leiden as quickly as possible while working part time in Amsterdam. Dijkstra became the first programmer in the Netherlands, representing his nation. The role was so new that he was not permitted to use it as his occupation on his marriage certificate, being told to write “theoretical physicist” instead.

The new Armac computer was completed in 1956, based on Dijkstra’s programming. For its “festive opening”, as Dijkstra described it, the machine would need to run a programme which would show off its capabilities to an audience of non-specialists—Dijkstra told Frana in the 2001 interview: “you have to have a problem statement that non-mathematicians can understand; they even have to understand the answer”.

Whilst taking a break from a shopping trip in Amsterdam, Dijkstra came up with the problem, and the answer. He sat, drinking coffee with his fiancée, later wife, Ria (herself a mathematician and programmer). Over the course of twenty minutes, without pencil and paper, Dijkstra invented the shortest path algorithm to find the shortest way to travel between two places. He used cities in the Netherlands as a guide, reducing the number of cities to 64 to make the coding more efficient.

Mark starting vertex as 0.
Consider all neighbours of this vertex, calculate their distance away from the start.
Now visit every one of these neighbours and repeat the process, updating distances if they become shorter, filtering your way across the network.
Once your destination vertex is visited in this way, you can stop. You’ll have the shortest distance from the start.

A fortuitous by-product of this algorithm, which was eventually published in 1959, is that the shortest distance to every vertex from the start is calculated along the way.

This algorithm is used today in such technologies as GPS, route planning and phone networks. He was ahead of his time. Dijkstra appreciated how his work, and the work of those that followed him, would impact on society. He wrote programs for computers that were still being built, and encouraged programmers to write code without bugs so that debugging would not be needed!

In his acceptance speech for the Turing Award, Dijkstra prophesised about the future of computing:

In their capacity as a tool, computers will be but a ripple on the surface of our culture. In their capacity as intellectual challenge, they are without precedent in the cultural history of mankind. — Dijkstra, The Humble Programmer 1972

Dijkstra’s work spanned over 40 years. He gained a PhD from the University of Amsterdam in computer science in 1959 with his thesis Communication with an automatic computer. From 1962 to 1984, Dijkstra was a professor of mathematics at the University of Eindhoven. Here he further developed what came to be known as structural programming–a method for writing code which was clear, logical and elegant–a personification of Dijkstra himself. He also developed THE operating system (named after Technische Hogeschool Eindhoven, the Dutch name for the University of Eindhoven) which was the precursor to many operating systems in use today.

Dijkstra moved to the University of Texas in 1984, and remained there until his retirement in 1999. He died in the Netherlands in 2002. Dijkstra’s twenty-minute coffee break, another in his long series of coincidences, changed the world: his algorithm providing roots for new branches of mathematics and computer science.