Comment appliquer un algorithme de Dijkstra pour trouver un MST de telle sorte que l'arbre résultant ait un bord entre deux sommets donnés? (Ex: MST doit inclure une arête entre X et Y)Problème d'algorithme de Dijkstra
Merci
algorithme de Dijkstra est pour les chemins les plus courts (non MST), mais quelque chose de similaire à l'algorithme de Dijkstra, tel que modifié pour trouver un arbre couvrant minimal, est appelé algorithme de Prim. L'algorithme de Prim garde un arbre qui se développe jusqu'à ce qu'il couvre tout le graphe. La contrainte supplémentaire introduite ici ne pose pas beaucoup de problèmes: vous commencez simplement avec X-Y comme arbre. Plus précisément, étant donné que votre MST doit inclure le bord (X, Y) (s'il y a plusieurs arêtes de ce type), commencez par votre arbre ayant deux nœuds X et Y et le bord entre eux. Maintenant, à chaque étape, choisissez le plus petit bord (u, v) où vous êtes dans votre arbre et v dehors, ajoutez le nœud v et le bord (u, v) à votre arbre, et répétez.
+1 pour l'algorithme de Prim, très intéressant http://en.wikipedia.org/wiki/Prim%27s_algorithm –
Je peux simplement le faire dans Prim's mais le problème est d'utiliser Dijkstra pour trouver MST avec la contrainte mentionnée – coder9
Dijkstra ne vous trouvera pas un MST. Considérons le graphique simple avec 3 bords, AB coûte 4, BC coûte 5, et AC coûte 7. Dikjstra voudra toujours choisir AB et AC pour un chemin le plus court de AC de 7, mais un poids total de 12 arbres. Mais la volonté de Prim toujours choisir AB et BC, puisque le poids total de l'arbre est 9, même si le chemin le plus court de A à C est également 9. Les algorithmes sont très similaires, mais je n'appellerai jamais quelque chose qui se comporte comme la Dijkstra plus tardive. Si c'est un travail à faire, peut-être que le prof veut juste que vous réalisiez à quel point Dijkstra est facile dans l'algorithme de Prim? –
Dijkstra ne trouve pas le MST pour commencer. – Waldheinz
oui. Il doit être modifié dans ce cas – coder9
Cochez cette [question] (http://stackoverflow.com/questions/1909281/use-dijkstras-to-find-a-minimum-spanning-tree) –