Algorithme de Prim

L'algorithme de Prim est un algorithme glouton qui calcule un arbre couvrant minimal dans un graphe connexe pondéré et non orienté. En d'autres termes, cet algorithme trouve un sous-ensemble d'arêtes formant un arbre sur l'ensemble des sommets du graphe initial et tel que la somme des poids de ces arêtes soit minimale. Si le graphe n'est pas connexe, alors l'algorithme détermine un arbre couvrant minimal d'une composante connexe du graphe.

Historique 
L'algorithme 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. Ainsi, il est parfois appelé DJP algorithm, Jarník's algorithm, Prim–Jarník algorithm, ou Prim–Dijkstra algorithm.

Principe 

L'algorithme consiste à faire croître un arbre depuis un sommet. On part d'un sous-ensemble contenant un sommet unique. À chaque itération, on agrandit ce sous-ensemble en prenant l'arête incidente à ce sous-ensemble de coût minimum. En effet, si l'on prend une arête dont les deux extrémités appartiennent déjà à l'arbre, l'ajout de cette arête créerait un deuxième chemin entre les deux sommets dans l'arbre en cours de construction et le résultat contiendrait un cycle.

Exemple 

À droite, on donne un exemple d'exécution de l'algorithme de Prim.

Pseudo-code 
Le pseudo-code de l'algorithme de Prim est similaire à celui de l'algorithme de Dijkstra et utilise le type abstrait file de priorité.
  fonction prim(G, s)
        pour tout sommet t
               cout[t] := +∞
               pred[t] := null
        cout[s] := 0
        F := file de priorité contenant les sommets de G avec cout[.] comme priorité 
        tant que F ≠ vide
             t := F.defiler
             pour toute arête t--u avec u appartenant à F
                 si cout[u] >= poids de l'arête entre les sommets t et u
                        pred[u] := t
                        cout[u] := poids de l'arête entre les sommets t et u
                        F.notifierDiminution(u)
                         
        retourner pred
Au début tous les sommets sont dans la file de priorité. La priorité est donnée par cout[.]. Autrement dit, le sommet possédant la plus faible valeur dans le tableau cout[.] sortira en premier de la file. On retire un à un les sommets de la file de priorité. Le tableau pred[.] contient le prédécesseur d'un sommet dans l'arbre en construction. L'algorithme retourne le tableau pred qui représente l'arbre couvrant de poids minimum.

Complexité 
On effectue  opérations défiler et  opérations réduire priorité, où  est le nombre de sommets dans le graphe et  est le nombre d'arcs dans le graphe. Si l'on regarde la complexité de ces deux opérations avec trois possibilités de files de priorités, on obtient les complexités ci-dessous :

Preuve de correction 
Soit G un graphe connexe pondéré. À chaque itération de l'algorithme de Prim, on trouve une arête qui connecte un sommet dans un sous-graphe à un sommet à l'extérieur du sous-graphe. Puisque G est connexe, il y aura toujours un chemin vers tous les sommets. La sortie Y de l'algorithme de Prim est un arbre, parce que chaque sommet (sauf le premier) est relié à exactement un prédécesseur.

Soit Ai l'ensemble des i premières arêtes ajoutées à l'arbre Y par l'algorithme de Prim et A0 = {}. 
On va montrer que, pour chacun des Ai, il existe un arbre couvrant minimal de G contenant Ai. Alors il existera un arbre couvrant minimum qui contiendra Y et sera donc Y.
Pour ce faire, supposons qu'il existe un premier ensemble Ak tel qu'aucun arbre couvrant minimal ne contient Ak. Soit e l'arête qui appartient à Ak mais n'appartient pas à Ak-1, soit Y1 un arbre couvrant minimum du graphe G qui contient toutes les arêtes d' Ak-1 et soit S l'ensemble de sommets reliés par les arêtes d' Ak-1. 
Une extrémité de l'arête e est dans l'ensemble S et l'autre n'est pas. Puisque l'arbre Y1 est un arbre couvrant du graphe G, il y a un chemin dans l'arbre Y1 joignant les deux extrémités de e. Lorsque l'on se déplace le long du chemin, on doit rencontrer une arête f qui joint un sommet de S à un sommet qui n'est pas dans l'ensemble S. Alors, à l'itération où l'arête e a été ajoutée à l'arbre Y, l'arête f pourrait aussi avoir été ajoutée et elle serait ajoutée au lieu de e si son poids était moins que celui de e, et puisque l'arête f n'a pas été ajoutée, nous concluons que

Soit Y2 l'arbre obtenu en enlevant l'arête f et en ajoutant l'arête e à l'arbre Y1. Il est facile de montrer que l'arbre Y2 est un arbre couvrant et le poids total de ses arêtes n'est pas supérieur à celui de l'arbre Y1 et que Y2 contient toutes les arêtes d' Ak. On arrive à une contradiction, car on a supposé qu'il existe un ensemble Ak tel qu'aucun arbre couvrant de poids minimum ne contient les arêtes d' Ak. C'est donc que l'hypothèse faite est fausse.

Notes et références

Voir aussi

Bibliographie 
 J.-F. Hêche, ROSO-EPFL, Cours SC de recherche opérationnelle : Quelques problèmes classiques en théorie des graphes

Liens internes 
 Algorithme de Kruskal
 Algorithme de Borůvka

Prim