Stories
Slash Boxes
Comments
NOTE: use Perl; is on undef hiatus. You can read content, but you can't post it. More info will be forthcoming forthcomingly.

All the Perl that's Practical to Extract and Report

use Perl Log In

Log In

[ Create a new account ]

waltman (335)

waltman
  (email not shown publicly)

Journal of waltman (335)

Monday February 23, 2009
11:34 PM

They don't write them like that anymore

[ #38541 ]
Today I found myself needing a citation for the Floyd-Warshall algorithm. This is a famous algorithm in graph theory that simultaneously finds the shortest path between every pair of nodes in a weighted, directed graph. (A nice description of Floyd-Warshall is on Wikipedia).

Modern algorithms textbooks often devote entire chapters to shortest path algorithms, so I was surprised to see that the citation said it was only a page. I thought it might have been a misprint and I pulled up the original CACM article from the ACM website. Not only was Floyd's article less than a page, it was only about 1/4 of a column of a page. It was only 21 lines, including title and comments!

Floyd's article was published back in 1962, when men were men, computers filled buildings, and the CACM published an Algorithms column consisting mainly of short algorithms submitted by readers. The private sector seemed more involved in basic computer research then than they are now; there are algorithms in this issue submitted by researchers at Control Data, Burroughs, Sperry, and the US Steel Applied Research Lab. As for the code, I thought it was a Pascal-like pseudocode, but it turns out to be ALGOL-60.

Ah, the good old days...

The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
 Full
 Abbreviated
 Hidden
More | Login | Reply
Loading... please wait.