L’algorithme de prime fus développé en 1930 par le Mathématicien Vojtech Jarmik avant d’être repris par Robert C Prim et Edsger Dijkstra en 1959.
L’algorithme consiste à parcourir tous les sommets d’un graphe en empruntant le plus court chemin possible, pour cela l’algorithme va partir d’un sommet et créer 3 tableaux. Le premier contient les sommets ouverts open(), le deuxièmes les sommets fermés close() et le troisième les sommets retenus s().
L’algorithme va commencer par ajouter toutes les arrêtes reliés à son sommet de départ dans open() et va ajouter à s() l’arrête dont le poids est le plus faible (Bien évidement cette même arrête est retirée de open()). L’algorithme va ensuite répéter la même opération en ajoutant les nouvelles arrêtes à open(). Lorsqu’une arrête est toujours dans open() mais qu’elle même à un sommet déjà exploré elle est ajoutée dans close().
L’algorithme se répète ainsi jusqu’à que tous les sommets soit reliés par les arrêtes de s().

Exemple

En rouge: Les arrêtes présentent dans s()

En bleu: Les arrêtes présentent dans close()

En vert: Les arrêtes présentent dans open()

 

123456