25 Feb
2018
25 Feb
'18
7:16 p.m.
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