Spanning Tree minimum en utilisant l'algorithme de Dijkstra

Dijkstra ne peut pas être utilisé pour trouver le MST d'un graphe. C'est un algorithme gourmand qui trouve le chemin le plus court entre les nœuds. Ainsi, bien que cela minimise le coût d'aller d'un nœud à l'autre, il ne produira pas toujours le MST pour l'ensemble du graphe. Le poids total des arêtes de Dijkstra peut ne pas être égal au poids total du MST.

L'algorithme de Dijkstra lui-même ne trouvera pas avec précision l'arborescence minimale d'un graphique. Il est destiné à trouver le chemin le plus court entre un sommet source et tous les autres sommets du graphe. Pour cette raison, à chaque étape, l'algorithme de Dijkstra sélectionnera avidement l'arête suivante la plus proche du sommet source. Il continue jusqu'à ce que le sommet source soit connecté à tous les autres sommets du graphique. Par conséquent, à chaque étape, le graphe courant qui est produit est un arbre couvrant du graphe précédent, mais la somme des poids des arêtes n'est pas minimisée car elle ne considère que les sommets par rapport au sommet source.

Cependant, l'algorithme de Prim, qui est utilisé pour produire un arbre couvrant minimum, est très similaire dans sa procédure à l'algorithme de Dijkstra. Cependant, à chaque étape, au lieu de choisir l'arête suivante la plus proche du sommet actuel, il sélectionne goulûment l'arête suivante la plus proche de n'importe quel sommet actuellement dans l'arbre couvrant minimum (le graphique qu'il produit) à cette étape. < / p>

Utilisez boost :: graph < / code> bibliothèque. Consultez la table des matières ici . En particulier, il contient les algorithmes Kruskal minimum spannig tree et Prim arbre minimum de spannig .