In an oral history interview with Philip Frana in 2001, Edsger Dijkstra remembers the circumstances of the discovery of his shortest path algorithm:
One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years late. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame.
…
It was originally published in 1959 in a German article in Numerische Mathematik. F.L. Bauer had founded that journal and he was soliciting for articles. Now, at the time, something like an algorithm for the shortest path, that 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? So that is why it remained unpublished, but when Bauer asked whether we could contribute something, I said, yes, I could, because in the mean time I had also designed the shortest subspanning tree. I had done that 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 an article “A note on two problems in connection with graphs” or something like that. But now, when I went to my ophthalmologist — and to the best of my knowledge 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 last November [2000].
Edsger W. Dijkstra, OH 330. Oral history interview by Philip L. Frana, 2 August 2001, Austin, Texas. Charles Babbage Institute, University of Minnesota, Minneapolis. http://purl.umn.edu/107247 Pp. 5–6 of PDF.
I recommend the full interview, which touches on many matters of interest in the history of computers and computer science. The site itself contains transcripts of several hundred interviews in this field, conducted between 1973 and (to date) 2009.
