Edsger Dijkstra

Edsger Dijkstra (“Dykstra”) 1930-2002

GPS route finders and phone switching networks both have to solve a hard problem: given a diagram of roads or connections, how do you find the shortest route between two points? In the early days of computing in 1959, Edsger Dijkstra invented a systematic method of  doing this that became known as Dijkstra’s Algorithm. It is still the basis of much of the software that routes calls and texts through the phone network and emails through the internet, as well as being at the heart of the route finder in your car.

Dijkstra was a university professor for much of his life, which spanned the era when basic methods of computer programming were still being worked out. He kick-started what became known as the Structured Programming movement. Up until the 1970s, programmers often made liberal use of the Go To statement in their programs, which instructs the computer to jump from one part of the program to another. In a letter in 1968 to the journal of the Association for Computing Machinery entitled Go To Statement Considered Harmful,  Dijkstra pointed out that this resulted in programs that were difficult to follow, and therefore very difficult for other programmers to change - or even for the original programmer to get right in the first place.  He argued that instead, a program should take the computer through a sequence of nested loops and alternatives. As a result, most modern programming languages do not provide a way of performing an arbitrary jump, but instead provide rich facilities for building a program out of nested blocks.

Getting a computer to run more than one program at a time is commonplace now, and owes a great deal to Dijkstra’s  ideas. He invented the Semaphore, the mechanism that allows concurrent programs to share a single resource. For example, two programs can use the same printer without their output being mixed up on the same page, and can use the same internet connection without their messages getting confused.