25 Feb
2018
25 Feb
'18
7:59 p.m.
On Sun, Feb 25, 2018 at 08:16:36AM -0500, Doug McIlroy wrote:
On the subject of independent (re)discovery, it is interesting to note
that the second problem in Dijkstra's paper describes a solution to
the minimum spanning tree problem that was already pubslished in 1957
by Prim and in 1930 by Jarnik. I guess that in those days searching for
existing solutions wasn't as easy as it is now.
-Otto
But a note on
Dijkstra's algorithm: Moore and Dijsktra both published
in 1959.
I was off by one on the year, but the sign of the error is debatable.
Moore's paper was presented in a conference held in early April, 1957,
proceedings from which were not issued until 1959. I learned about it
from Moore when I first I met him, in 1958. Then, he described the
algorithm in vivid, instantly understandable terms: imagine a flood
spreading at uniform speed through the network and record the
distance to nodes in order of wetting.
But it is documented Dijkstra's algorithm
has been invented and used
by him in 1956.
Taking into account the lead time for conference submissions, one
can confidently say that Moore devised the algorithm before 1957.
I do not know, though, when it first ran on a Bell Labs computer.
That said, Moore's paper, which presented the algorithm essentially
by example, was not nearly as clear as the capsule summary he gave
me. It seems amateurish by comparison with Dijkstra's elegant treatment.
Dijkstra's name has been attached to the method with good reason.
Doug