BIOGRAPHY OF EDSGER W. DIJKSTRA
Edsger Wybe Dijkstra was born on May 11, 1930 in Rotterdam, Netherlands. Born to a chemist and a mathematician (father and mother, respectively), it was inevitable for Dijkstra to excel in education. “I asked my mother whether mathematics was a difficult topic. She said to be sure to learn all the formulas and be sure you know them. The second thing to remember is if you need more than five lines to prove something, then you’re on the wrong track.” [1] When he turned 12, he entered a high school especially for those extremely gifted students. He studied a variety of courses including, of course, chemistry and mathematics along with a variety of foreign language classes and biology. He attended CambridgeUniversity in 1951 and started working at the Mathematical Centre in Amsterdam which continued to peak his interest in computer science and programming. While attending the Mathematical Centre he had to make a decision whether he wanted to be a theoretical physicist or whether he wanted to pursue his passion of computer programming. The decision was not easy as programming was not a well known and respectable profession. He finally chose programming and Dijkstra received a PhD in 1959 from the University of Amsterdam with his emphasis on the assembly language. In the 1970’s Dijkstra began working at Burroughs Corporation as a research fellow, then in 1984 he held the Schlumberger Centennial Chair in Computer Science at The University of Texas at Austin until his retirement in 2000.
Dijkstra’s contributions made huge impacts to the world of computer science. “His ground-breaking contributions ranged from the engineering side of computer science to the theoretical one and covered several areas including compiler construction, operating systems, distributed systems, sequential and concurrent programming, software engineering and graph algorithms.”[2]In 1959, Dijkstra’s paper titled A Note on Two Problems in Connexion with Graphs was published where he describes the solution to shortest path problem. One of Dijkstra’s first and biggest contributions to the mathematical world is known as the “Shortest – Path Algorithm“ or simply Dijkstra’s algorithm. “The algorithm solves a shortest path problem for a directed graph with nonnegative edge weights.” [3] Furthermore, a shortest path problem in mathematics is defined by “finding a path between two vertices such that the sum of the weights of its constituent edges is minimized.” [4] In the computer science world the algorithm is downplayed by competing algorithms. “Although the algorithm is very popular in the OR/MS literature, it is generally regarded as a "computer science method". Apparently this is due to three factors: (a) its inventor was a computer scientist (b) its association with special data structures, and (c) there are competing OR/MS oriented algorithms for the shortest path problem.” [5]
The following is the formal definition of Dijkstra’s algorithm:
G – arbitrary connected graph
v0 – is the initial beginning vertex
V – is the set of all vertices in the graph G
S – set of all vertices with permanent labels
n – number of vertices in G
D – set of distances to v0
C – set of edges in G
Dijkstra’s Algorithm (graph G, vertex v0)
{
S={v)}
For I = 1 to n
D[i] = C[v0,i]
For I = 1 to n-1
Choose vertex w in V-S such that D[w] is minimum
Add w to S
For each vertex v in V-S
D[v] = min(D[v], D[w] + C[w,v])
}[6]
Starting at a particular vertex, the algorithm works through the graph until all vertices (nodes) have been reached and weight has been determined for all of the nodes of the graph. The following is a simple representation of how the algorithm works:
Consider there are 3 possible routes between A and E.
Your choices are ABE, ABCE and ABDE. We start
at vertex A to find the shortest route.
Next we determine the next vertex to be
added to the path. Since we only have one choice we
will add B to our path which gives us a distance of 3.
Step 3 compares the weights between BC, BE, and BD
to determine the nextvertex to be added to the path.
In the following diagramyou will notice C is added as
the next vertex which willgive us a distance of 4.
Step 4 compares the weights between CE, BE, and BD
to determine the next vertex to be added. It is determined
that D is the next vertex added giving us a distance of 5.
Finally step 5 compares the weights between CE, BE, and
DE. It is determined that DE is the last length to be added,
which would make ABDE the shortest path with a length
of 6.
In reality, Dijkstra’s algorithm is used in many real life situations to figure out the shortest path to save time and money. His algorithm has been widely used in networkcommunication, interstate/roadway planning, and air flight planning. The following example will demonstrate a realistic view at determining the shortest path for network traffic between Los Angeles, CA and New York, NY.
Suppose a wide area network must determine the shortest path for network activity to flow from L.A to New York City based on cost and speed. The priorities (weights) of the diagram would be determined by the speed of the network connection. There are considerations when determining the shortest path that could impact time and money. The following are a few considerations the company would consider:
- Line Capacity
- 56K
- T1 (1.544 Mbps)
- T3 (45 Mbps)
- Transit Delay
- Number of Routers
- Time of Day
- Data Type
- Video
- Database
- Voice
Suppose there are a variety of potential routes the company is considering. Knowing the companies priorities and considerations, they will need to discover the shortest path from Los Angeles to New York City. The following is a graph of the routes with the weights applied according to the speed of the network connection.
Applying Dijkstra’s algorithm to find the shortest path based upon speed is as follows:
LA to
Seattle- LA to Seattle
New Hampshire- LA to Seattle to New Hampshire
Denver- LA to Denver
Dallas- LA to Dallas
New York- LA to Dallas to New York
Denver to
Seattle- Denver to LA to Seattle
New Hampshire- Denver to New York to New Hampshire
LA- Denver to LA
Dallas- Denver to Dallas
New York- Denver to New York
Considering the possibility of a router going down, Dijkstra’s algorithm can quickly recalculate the most efficient paths. The following shows the shortest path based upon speed if Dallas went offline:
LA to
Seattle- LA to Seattle
New Hampshire- LA to Seattle to New Hampshire
Denver- LA to Denver
New York- LA to Denver to New York
Denver to
Seattle- Denver to LA to Seattle
New Hampshire- Denver to New York to New Hampshire
LA- Denver to LA
New York- Denver to New York
Along with Dijkstra’s algorithm, he was well known for his essays and papers on programming. He developed many concepts and algorithms in the areas of computer science and mathematics which are a compilation of manuscripts called EDWs. The collection of these manuscripts can be found in books such as Selected Writings on Computing: A personal perspective or available on the web at . They included topics ranging from his findings on self-stabilization and the theorem about odd powers and odd integers to trip reports (where he would describe various places he would attend conferences and lectures). Many of Dijkstra’s accomplishments discussed from here on out in this paper were based off his manuscripts.
About 5 years after Dijkstra started his work on shortest path algorithms, he became a pioneer in his study of distributed computers which included semaphore and mutual exclusion. Dijkstra began testing his theories on the X1 and X8 (successors to ARAMAC). “Dijkstra arranged each device attached to the computer to perform its tasks one step at a time, while exchanging messages with the computer. In computer jargon, these are called communicating sequential processes.” [7] In the computer world the problem comes when trying to synchronize these processes that are accessing the same piece of data. Like a database, you must find a way to avoid collision of the same data. To avoid the collision Dijkstra used a semaphore analogy of train signaling system. The semaphore is used to only allow one train to pass at a time when they share a similar piece of track in their route. This use of a semaphore is called mutual exclusion. Thus, Dijkstra took this analogy and applied it to the interaction between a keyboard and a computer. The buffer is the medium between the two and only one of them should be writing or reading at any one time.
Along the lines of mutual exclusion would be Dijkstra contributions to distributed computing. In his paper Self-Stabilization in Spite of Distributed Control, Dijkstra talks about the state a computer in a distributed system must attain to properly access data without conflicting with others. Dijkstra states “I call a system “self-stabilizing” when, regardless of its initial state, it is guaranteed to arrive at a legitimate state in a finite number of steps.” [8] You can think of Dijkstra solution as a token ring being passed around the network. One can access data only if it has the token. The solution requires at least on computer in the network to obtain the token at all times. Dijkstra states “Self-stabilizing systems with distributed control do exist in the sense that local decisions force the system towards satisfying and then maintaining a global requirement. In particular, local mutual exclusion is a sufficient building block for eventually achieving mutual exclusion globally.” [9]Early works of self-stabilization did not take into account the detection of faults instead proceeded to obtain a legitimate state.
Through all of Dijkstra’s research on multi-process synchronization he came up with an examination question for his students at EinhovenTechnicalUniversitywhere a set of computers where fighting for the access to the same data stores. The examination problem would later be known as the dining philosopher’s problem by Tony Hoare. The problem addresses the issues involved with using a token ring solution for multi-process synchronization. The problem describes how 5 philosophers are sitting around a table with a bowl of rice in front of each of them and a chopstick between each bowl.
They are allowed to do one of 2 things at any given time: think or eat. In order to eat, each philosopher must have 2 chopsticks. As in the token ring solution there are 3 situations that can occur:
- Deadlock: This occurs when all the philosophers obtain the chopstick to the right of them and endlessly wait for the chopstick to their left.
- Starvation: This occurs when one of the philosophers decided not to eat while another philosopher grabs his chopstick, but causing an issue when the first philosophers makes an attempt to eat but his chopstick is never released.
- Lack of Fairness: This occurs when one some philosophers get to eat more often than others.
In Dijkstra’s paper Hierarchical ordering of sequential processes, he begins to discuss solutions to the problems of deadlocking and starvation. He starts by exploring the idea of those programs needing to be run simultaneously; they should run on separate processors in order to keep from interfering with one another. As Dijkstra proceeds to describe the solution of mutual exclusion the most critical aspect is network communication between the processors and the data store. Dijkstra proceeds to show his proof to the problem in which the solution he describes combines the use of multiple semaphores and applying the restrictions of synchronization.
In 1968, he wrote a paper A case against the GO TO statement with his viewpoint of the harmfulness of using GO TO statements in programming. Dijkstra’sbelieves the GO TO statement in programming will eventually only hinder the program rather than help. He describes the progress of a process and how this process is more difficult to determine once a programmer introduces the use of GO TO statements. A program with well defined statements (including loops, if else and repetition clauses), is much easier to reproduce the action and determine the action in which it failed. With GO TO statements, this task becomes more difficult to determine progress with the program. “If we wish to count the number, n say, of people in an initially empty room, we can achieve this by increasing n by one whenever we see someone entering the room. In the in-between moment that we have observed someone entering the room but have not yet performed the subsequent increase of n, its value equals the number of people in the room minus one.” [10]
In 1970, he began publishing his opinion on formal verification. Instead of developing a program and proving its purpose and accuracy after the fact, Dijkstra believed the concept behind the program should be done simultaneously to develop insight into the program and why it was created. As computers and software have grown exponentially in their abilities and power to solve complex algorithms, the individual behind the programmer has not exponentially grown as well. Dijkstra’s way of thinking is known as program deviation. In his book, A Discipline of Programming, Dijkstra takes many algorithms and applies his idea of program deviation in which he starts with a proof to a problem and develops the appropriate program to solve it. He believes that a program should work hand in hand with a programmer to solve the problem, not tobe so complex you cannot restructure the program into a mathematical algorithm. “Today a usual technique is to make a program and then to test it. But: program testing can be a very effective way to show the presence of bugs, but is hopelessly inadequate for showing their absence. The only effective way to raise the confidence level of a program significantly is to give a convincing proof of its correctness.” [11]
Dijkstra retired in 2000 after pioneering many concepts and thoughts on the computer science and mathematical industries. After a long battle with cancer, Edsger W. Dijkstra passed away in Nuenen, The Netherlands on August 6, 2002. A year after his passing the ACM (Association for Computing Machinery) renamed the PODC Influential Paper Award, in which Dijkstra won for his extensive work on distributed computing, to the Dijkstra Prize in his honor.
Bibliography
Dijkstra, E. W., & Scholten, C. S. (1990). Predicate Calculus and Program Semantics. New York City: Springer-Verlag New York Inc.
Dijkstra, Edsger W. (1982). Selected Writings on Computing: A Personal Perspective. New York, NY: Spinger-Verlag New York Inc.
Dijkstra, Edsger W. (1976). A Discipline of Programming. Englewood Cliffs, NJ: Prentice-Hall, Inc..
Shasha, D, & Lazere, C (1995). Out Of Their Minds: The Lies and Discoveries of 15 great Computer Scientists. New York City: Copernicus.
Dijkstra's Algorithm. Retrieved March 05, 2007, from Dijkstra Web site:
Dijkstra, Edsger W. (1965). A Note of Two Problems in Connexion with Graphs. Retrieved March 17, 2007, Web site:
Knuth, Donald E. (December 1974). Structured Programming with go to Statements. Computing Surveys, 6, Retrieved March 19, 2007, from
Dijkstra, Edsger W. Hierarchical Ordering of Sequencial Processes. Retrieved March 19, 2007, Web site:
Dijkstra, Edsger W. (1972). The Humble Programmer. Retrieved March 22, 2007, Web site:
Freedom at the Mathematisch Centrum. Retrieved March 24, 2007, from Mathematical Center Amsterdam Web site:
E.W. Dijkstra Archive: Home page. Retrieved March 22, 2007, from E.W. Dijkstra Archive The Manuscripts of Edsger W. Dijkstra Web site:
Edsger Dijkstra. In Wikipedia [Web]. Wikimedia Foundation, Inc. Retrieved March 3, 2007, from
Dijkstra's Algorithm. In Wikipedia [Web]. Wikimedia Foundation, Inc. Retrieved March 3, 2007, from
Shortest Path Problem. In Wikipedia [Web]. Wikimedia Foundation, Inc. Retrieved March 20, 2007, from
(2006). Retrieved March 18, 2007, from Association for Computing Machinery: A.M. Turing Award Web site:
Edgser W. Dijkstra. Retrieved March 18, 2007, from Edsger Wybe Dijkstra Web site:
Edsger W. . Retrieved March 5, 2007, from Edsger W. Dijkstra Web site:
Dijkstra's . Retrieved March 5, 2007, from Dijkstra's algorithm Web site:
A Guide to the Edsger W. Dijkstra Papers, 1948-2002. Retrieved March 18, 2007, from The Center for American History: The University of Texas at Austin Web site:
Razavi, Roozbeh Retrieved March 5, 2007, from How Routing Algorithms Work Web site:
Dijkstra's Algorithm. Retrieved March 20, 2007, from Dijkstra's Algorithm Web site:
Dijkstra's algorithm: Information form Answers.com. Retrieved March 20, 2007, from Dijkstra's Algorithm Web site:
Apt, Krzysztof R. (2002). Obituray Edsger Wybe Dijkstra (1930-200): A Portraitof a Genius. Formal Aspects of Computing, 14, Retrieved March 20, 2007, from
Dijkstra, Edsger W. (1972). Retrieved March 20, 2007, from The Humble Programmer Web site:
Dijkstra, Edsger W. (1968). Go To Statement Considered Harmful. Communications of hte ACM, 11, Retrieved March 22, 2007, from
[1] Shasha, D, & Lazere, C (1995). Out Of Their Minds: The Lies and Discoveries of 15 great Computer Scientists. New York City: Copernicus. Pg. 55
[2]Apt, Krzysztof R. (2002). Obituray Edsger Wybe Dijkstra (1930-200): A Portraitof a Genius. Formal Aspects of Computing, 14, Retrieved March 20, 2007, from
Pg 93
[3] Dijkstra's Algorithm. In Wikipedia [Web]. Wikimedia Foundation, Inc. Retrieved March 3, 2007, from
[4]Shortest Path Problem. In Wikipedia [Web]. Wikimedia Foundation, Inc. Retrieved March 20, 2007, from
[5]Dijkstra's Algorithm. Retrieved March 05, 2007, from Dijkstra Web site:
[6] Dijkstra's Algorithm. Retrieved March 20, 2007, from Dijkstra's Algorithm Web site:
[7] Shasha, D, & Lazere, C (1995). Out Of Their Minds: The Lies and Discoveries of 15 great Computer Scientists. New York City: Copernicus. Pg 61
[8] Dijkstra, Edsger W. (1982). Selected Writings on Computing: A Personal Perspective. New York, NY: Spinger-Verlag New York Inc. Pg 42
[9] Dijkstra, Edsger W. (1982). Selected Writings on Computing: A Personal Perspective. New York, NY: Spinger-Verlag New York Inc. Pg
[10] Dijkstra, Edsger W. (1968). Go To Statement Considered Harmful. Communications of hte ACM, 11, Retrieved March 22, 2007, from
[11]Dijkstra, Edsger W. (1972). Retrieved March 20, 2007, from The Humble Programmer Web site: Pg 26