[Reflections on “A note on two problems in connexion with graphs”

Dijkstra E W. A Note on Two Problems in Connexion with Graphs

Numerische Mathematik 1: 269-271, 1959

[Mathematisch Centrum, Amsterdam]

Abstract. We consider a graph with $n$ vertices, all pairs of which are connected by an edge; each edge is of given positive length. The following two basic problems are solved.

Problem 1. Construct the tree of minimal total length between the $n$ vertices. (A tree is a graph with one and only one path between any two vertices.)

Problem 2. Find the path of minimal total length between two given vertices.

Edsger W.Dijkstra

Burroughs/Eindhoven University of Technology

Plataanstraat 5

5671 AL Nuenen, The Netherlands

I found my solution to the second problem in 1956 after having invented the problem first. At the time I was the main programmer of the Mathematical Centre in Amsterdam, where the construction of its second automatic computer was on the verge of completion, and for the celebration of its inauguration we needed a nice demonstration: it should solve a problem that could be easily stated to a predominantly lay audience. For the purpose of the demonstration I drew a slightly simplified map of the Dutch railroad system, someone in the audience could ask for the shortest connection between, say, Harlingen and Maastricht, and the ARMAC would print out that shortest route town by town. The demonstration was a great success; I remember that I could show that inversion of source and destination could influence the computation time required. The speed of the ARMAC and the size of the map were such that one minute always sufficed.

I found the solution to the first problem about a year later, when the next machine was under construction and I was asked whether I could minimize the amount of cable needed for the back-panel wiring, which had to connect pins tree-fashion. I remember its discovery more vividly than that for the shortest route: my wife and I were having a cup of coffee in front of some café at the sunny side of the Damrak. I found both solutions

unhampered by such mechanical aids as pencil and paper. It was clearly the more interesting of the two problems: looking at how my program represented trees, I rediscovered Cayley's Theorem that the number of different trees connecting n vertices equals $n^{n-2}$ (with a proof that was much nicer than Cayley's original one).

At the time I was fully aware of having found two gems: at the moment of discovery I was duly excited and I remember having presented them in a lecture. In retrospect it seems strange that I waited another two years before I submitted them for publication. The main reason was the absence of journals dedicated to automatic computing, something the foundation of Numerische Mathematik sought to remedy; I wrote and submitted my little article --my second one-- trying to assist the fledgling. Furthermore the Publish-or-Persh Syndrome had not reached the Netherlands yet.

The solutions, as elegant as effective, now belong to the intellectual baggage of any well-educated computing scientist, and the first one to publish them gets the credit and "collects" the references. I am pleased to see that by now the computing community is beginning to regard them as "common property" and to refer to them without mentioning my name: their birth has become history (as it should be).