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[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
L'algorithme[7] 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[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 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 :
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
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
- « O jistĂ©m problĂ©mu minimĂĄlnĂm. (Z dopisu panu O. BorĆŻvkovi) », sur dml.cz (consultĂ© le )
- 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, consultĂ© le )
- 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, consultĂ© le )
- (en) Robert Sedgewick et Kevin Daniel Wayne, Algorithms, Upper Saddle River, Addison-Wesley Professional, , 955 p. (ISBN 978-0-321-57351-3, BNF 44524965, présentation en ligne)
- (en) Kenneth Rosen, Discrete Mathematics and Its Applications 7th edition, McGraw-Hill Science, (lire en ligne)
- 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, consultĂ© le )
- (en) S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani, Algorithms
Voir aussi
Bibliographie
- J.-F. HĂȘche, ROSO-EPFL, Cours SC de recherche opĂ©rationnelle : Quelques problĂšmes classiques en thĂ©orie des graphes
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction Ă l'algorithmique, Dunod, [dĂ©tail de lâĂ©dition]