Algorithme de Prim

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Page d'aide sur l'homonymie Pour les articles homonymes, voir Prim.
Arbre couvrant de poids minimum

L'algorithme de Prim est un algorithme glouton qui calcule un arbre couvrant minimal dans un graphe connexe valué 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[modifier | modifier le code]

L'algorithme a été développé en 1930 par le mathématicien tchèque Vojtech Jarnik [1] puis a été redécouvert et republié par Robert C. Prim[2] et Edsger W. Dijkstra en 1959. Ainsi, il est parfois appelé DJP algorithm[3], Jarník's algorithm[4], Prim–Jarník algorithm[5], ou Prim–Dijkstra algorithm[6].

Principe[modifier | modifier le code]

L'algorithme[7] consiste à faire croître un arbre depuis un sommet. On commence avec un seul sommet puis à chaque étape, on ajoute une arête de poids minimum ayant exactement une extrémité dans l'arbre en cours de construction. En effet, si ses deux extrémités appartenaient 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[modifier | modifier le code]

Exécution de l'algorithme de Prim depuis le sommet A.

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

Pseudo-code[modifier | modifier le code]

Le pseudo-code[7] 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
                si cout[u] > poids(t--u)
                       pred[u] := t
                       cout[u] := poids(t--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[.]. 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é[modifier | modifier le code]

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:

File de priorité Graphe Complexité temporelle
liste ou tableau matrice d'adjacence
tas min binaire liste d'adjacence
tas de Fibonacci liste d'adjacence

Preuve de correction[modifier | modifier le code]

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 = {}. Nous allons démontrer par l'absurde que Y est un arbre couvrant minimal. 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. Puis que 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é et elle serait ajouté au lieu de e si son poids était moins que celui de e, et puisque l'arête f n'a pas été ajouté, 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[modifier | modifier le code]

  1. « O jistém problému minimálním. (Z dopisu panu O. Borůvkovi) », sur dml.cz (consulté le 26 décembre 2015)
  2. R.C. Prim, « Shortest connection networks and some generalizations », Bell System Technical Journal, The, vol. 36,‎ , p. 1389-1401 (ISSN 0005-8580, DOI 10.1002/j.1538-7305.1957.tb01515.x, lire en ligne)
  3. Seth Pettie et Vijaya Ramachandran, « An Optimal Minimum Spanning Tree Algorithm », J. ACM, vol. 49,‎ , p. 16–34 (ISSN 0004-5411, DOI 10.1145/505241.505243, lire en ligne)
  4. (en) Robert Sedgewick et Kevin Daniel Wayne, Algorithms, Addison-Wesley Professional, (ISBN 9780321573513, lire en ligne)
  5. (en) Kenneth Rosen, Discrete Mathematics and Its Applications 7th edition, McGraw-Hill Science, (lire en ligne)
  6. D. Cheriton et R. Tarjan, « Finding Minimum Spanning Trees », SIAM Journal on Computing, vol. 5,‎ , p. 724-742 (ISSN 0097-5397, DOI 10.1137/0205051, lire en ligne)
  7. a et b (en) S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Liens internes[modifier | modifier le code]