Jarník–Prim minimum spanning tree algorithm
Algoritmo de árbol recubridor mínimo de Jarník-Prim
- Date
- 1930 (Jarník); redescubierto en 1957 (Prim) y 1959 (Dijkstra) · confidence high
- Place
- Prague, Czechoslovakia (present-day Czechia)
- Credited to
- Vojtěch Jarník; rediscovered by Robert C. Prim (1957) and Edsger W. Dijkstra (1959)
- Field
- Knowledge & symbols
⚠️ Disputed: the sources disagree.
What was discovered
Jarník described a method to find the minimum-weight spanning tree of a graph: starting from any vertex, it adds at each step the cheapest edge connecting the growing tree to a new vertex. Prim and later Dijkstra independently rediscovered it.
The algorithm is known variously as Jarník's, Prim's, Prim-Dijkstra's or the DJP algorithm because of its several independent discoveries; Jarník's original 1930 work went unnoticed in the West for a long time.
What it led to
- Optimisation of telecommunication and transport networks
- Foundation of greedy algorithms in graph theory
- Comparison and combination with Kruskal's algorithm (1956)