[TUHS] RIP Claude Shannon

Otto Moerbeek otto at drijf.net
Sun Feb 25 23:59:27 AEST 2018


On Sun, Feb 25, 2018 at 08:16:36AM -0500, Doug McIlroy wrote:

> > 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

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



More information about the TUHS mailing list