Jarník’s (“Prim’s”) Algorithm

Introduction to Jarník’s (“Prim’s”) algorithm

The next oldest minimum spanning tree algorithm was first described by the Czech mathematician Vojtěch Jarník in a 1929 letter to Borůvka; Jarník published his discovery the following year. The algorithm was independently rediscovered by Joseph Kruskal in 1956, (arguably) by Robert Prim in 1957, by Harry Loberman and Arnold Weinberger in 1957, and finally by Edsger Dijkstra in 1958. Prim, Lobermand and Weinberger, and Dijkstra all (eventually) knew of and even cited Kruskal’s paper, but since Kruskal also described two other minimum spanning tree algorithms in the same paper, this algorithm is usually called “Prim’s algorithm,” or sometimes “the Prim/Dijkstra algorithm,” even though by 1958 Dijkstra already had another algorithm (inappropriately) named after him.

Methodology

In Jarník’s algorithm, the intermediate forest $F$ has only one nontrivial component $T$; all the other components are isolated vertices. Initially, $T$ consists of a single arbitrary vertex of the graph. The algorithm repeats the following step until $T$ spans the whole graph:

• Jarník: Repeatedly add $T$'s safe edge to $T$.