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

Get to know Jarník’s (“Prim’s”) algorithm and its applications in solving the minimum spanning trees problem.

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.


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

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

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy