Algorithme de Prim (1930)

L'Algorithme de Prim a été développé en 1930 par le mathématicien tchèque Vojtech Jarnik puis a été redécouvert et republié par Robert C. Prim et Edsger W. Dijkstra en 1959. Il consiste à trouver l'arbre couvrant minimum. Imaginez que vous devez relier plusieurs villes en électricité, câble téléphonique ou chemins de fer. Quelle solution me donne une distance totale minimum ?? (distance minimum ≈ argent minimum)  1️⃣️ On choisit un point au hasard. Il est le premier point de notre arbre. 2️⃣️ On choisit le point le plus proche de notre arbre afin de le relier. 3️⃣️ On répète l'étape 2 jusqu'à ce que tous les points soient dans notre arbre. La recherche du point le plus proche est la fonction cruciale de cet algorithme. D'elle, dépend la performance globale. Algorithmes similaires : Algorithme de Borůvka - Algorithme de Kruskal.