Il y a maintenant deux algorithmes couramment utilisés, l'algorithme de Prim et l'algorithme de Kruskal.
Edsger Wybe Dijkstra l'a redécouvert en 1959 et l'a appelé algorithme de Prim ; l'autre algorithme, appelé algorithme de Kruskal, a été pulvérisé par Joseph Kruskal en 1956.