12.4: Historical Notes

Last updated
Save as PDF

Page ID: 97947

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

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