designed the algorithm for the shortest path. As I said, it was a 20-minute invention. In fact, it was published in 1959, three years later. The publication is still quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. Without pencil and paper you are almost forced to avoid all avoidable complexities. Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame. I found it in the early 1960s in a German book on management science—“Das Dijkstra’sche Verfahren” [“Dijkstra’s procedure”]. Suddenly, there was a method named after me. And it jumped again recently because it is extensively used in all travel planners. 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.

When was the “shortest path” algo-
rithm originally published?

It was originally published in 1959 in Numerische Mathematik edited by F.L. Bauer. Now, at the time, an algorithm for the shortest path was hardly considered mathematics: there was a finite number of ways of going from A to B and obviously there is a shortest one, so what’s all the fuss about? It remained unpublished until Bauer asked whether we could contribute something. In the meantime I had also designed the shortest sub-spanning tree for my hardware friends. You know, on the big panel you have to connect a whole lot of points with the same copper wire because they have to have the same voltage. How do you minimize the amount of copper wire that connects these points? So I wrote “A note on two problems in connection with graphs.” 2 Years later when I went to my ophthalmologist—he did not even know that I was a computing scientist—he said, “Have you designed the algorithm for GPS?” It turned out he had seen the Scientific American of November 2000.10

how could you tell if early programs
were correct?

For those first five years I had always
been programming for non-existing
machines. We would design the instruc-
tion code, I would check whether I could
live with it, and my hardware friends
would check that they could build it. I
would write down the formal specifi-
cation of the machine, and all three of
us would sign it with our blood, so to
speak. And then our ways parted. All the
programming I did was on paper. So I
was quite used to developing programs
without testing them.

how was the computing culture in
America different?

Well, the American reaction was very different. When IBM had to develop the software for the 360, they built one or two machines especially equipped with a monitor. That is an extra piece of machinery that would exactly record when interrupts took place. And if something went wrong, it could replay it again. So they made it reproducible, yes, but at the expense of much more hardware than we could afford. Needless to say, they never got the OS/360 right.

in the mathematical
culture of those
days you had
to deal with infinity
to make your
topic scientifically
respectable.

the os/360 monitor idea would have
never occurred to a european?

No, we were too poor to consider it and we also decided that we should try to structure our designs in such a way that we could keep things under our intellectual control. This was a major difference between European and American attitudes about programming.

how did the notion of program proofs
arise?

In 1959, I had challenged my col-
leagues at the Mathematical Centre
with the following programming task.
Consider two cyclic programs, and in
each cycle a section occurs called the
critical section. The two programs
can communicate by single reads
and single writes, and about the rela-
tive speeds of the programs nothing
is known. Try to synchronize these
programs in such a way that at any
moment in time at most one of them
is engaged in its critical section.d I
looked at it and realized it was not
trivial at all, there were all sorts of side
conditions. For instance, if one of the
programs would stay for a very long
time in its noncritical section, the
other one should go on unhampered.
We did not allow ‘After-you-after-you’
blocking, where the programs would
compete for access to the critical sec-
tion and the dilemma would never be
solved. Now, my friends at the Math-
ematical Centre handed in their so-
lutions, but they were all wrong. For
each, I would sketch a scenario that
would reveal the bug. People made
their programs more sophisticated
and more complicated. The construc-
tion and counterexamples became
even more time-consuming, and I had
to change the rules of the game. I said,
“Sir, sorry, from now onward I only ac-
cept a solution with an argument why
it is correct.”
Within three hours or so Th. J.
Dekker came with a perfect solution
and a proof of its correctness. He had
analyzed what kind of proof would be
needed. What are the things I have to
show? How can I prove them? Having
d This is an implementation of the mutual ex-
clusion problem, which later became a corner-
stone of the THE multiprogramming system
[THE = Technische Hogeschool Eindhoven
( Technical University Eindhoven)].