Sunday, 19 April 2009

Hip Hip Hooray!

This year it has been 50 years since a Dutch Mathematician Edsger W. Dijkstra published his famous algorithm to solve the shortest path problem. Time for a celebration! Although not always visible, we depend on the algorithm every day. The algorithm has many examples, starting from the obvious application in the satellite navigation system in your car. But also less straight forward applications like in Internet routing protocols like IS-IS and OSPF, without it no Internet and you would not be able to read this blog entry.

Edsger Dijkstra was a brilliant computer scientist, who strang enough was not very found of using computers himself. He was well known for his use of a fountain pen, instead of a word processor. It has been said that he even went so far as to create his own ink because he was not happy with the quality of the ink that was available. Besides the Shortest Path algorithm he has many other accomplishments in the area of program correctness, mathematical methodology, algorithms, and systems. He considered the GOTO statement as disastrous as you can read from his article in the Communications of the ACM 11, 147-148 in 1968.

"For a number of years I have been familiar with the observation that the quality of programmers is a decreasing function of the density of go to statements in the programs they produce. More recently I discovered why the use of the go to statement has such disastrous effects, and I became convinced that the go to statement should be abolished from all "higher level" programming languages."

Dijkstra’s algorithm is a greedy algorithm to find the shortest distance from a starting point (or vertex) to any other point in a network (or graph). Actually it is an undirected weighted graph, the edges (or lines between points) all have a value, for example cost or duration. I have used it many times, even programmed in VB using GOTO statements (sorry Edsger!). It is any easy to use algorithm, and simple to programme or adapt to specific applications. It should be part of any OR practitioners toolbox. The obvious application is to calculate the travel times and shortest distances in a network. Based on the result infrastructure analysis and network design studies can be performed or optimal routes can be calculated. But I also used the same algorithm to generate schedules for bus drivers.

Dijkstra’s algorithm has many real world applications. One of them is in telephone networks. In a telephone network the lines have bandwidth; a phone call needs to be routed through the network via the highest BW. By representing the switching stations as vertices and the transmission lines as edges and the weight of edges to represent the band width, with Dijkstra’s algorithm we are able to find the best routing. This example is similar to the situation in which you want to plan your holiday or business visit. Given the available flights, airports and arrival and departure times, you can find out the earliest arrival time at your destination given the airport you want to start form and the start time with Dijkstra.

With Dijkstra’s algorithm we can put Operations Research into practice! Therefore three cheers for Edsger, Hip Hip Hooray, Hip Hip Hooray, Hip Hip Hooray!