Historical Notes

Kruskal's algorithm was published in 1956 by Joseph B. Kruskal in a three-page paper that appeared in Proceedings of the American Mathematical Society. Robert C. Prim published the algorithm that now bears his name the following year in The Bell System Technical Journal. Prim's paper focuses on application of the minimum weight (or length or cost) spanning tree problem to telephone networks. He was aware of Kruskal's prior work, as they were colleagues at Bell Laboratories at the time he published his paper. It turns out that Prim had been beaten to the punch by Czech mathematician Vojtěch Jarník in 1929, so some refer to Prim's algorithm as Jarník's algorithm. (It was later rediscovered by Dijkstra, so some attach his name as well, referring to it as the Dijkstra-Jarník-Prim algorithm.) Edsger Dijkstra published his algorithm for finding shortest paths in 1959 in a three-page paperThis is also the paper in which Prim's algorithm was published for the third time. Dijkstra was aware of Kruskal's prior work but argued that his algorithm was preferable because it required that less information about the graph be stored in memory at each step of the algorithm. appearing in Numerische Mathematik. In fact, Dijkstra's algorithm had been discovered (in an equivalent form) by Edward F. Moore two years earlier. His result appeared in Proceedings of an International Symposium on the Theory of Switching.