Utilisez de trouver un minimum Spanning Arbre de Dijkstra?

Question

de Dijkstra est généralement utilisé pour trouver la plus courte distance entre deux noeuds dans un graphe. Peut-il être utilisé pour trouver un couvrant arbre? Si oui, comment?

Edit:. Ce n'est pas devoirs, mais j'essaie de comprendre une question sur un vieux examen pratique

Answer 1

Strictement, la réponse est non. L'algorithme de Dijkstra trouve le chemin le plus court entre 2 sommets sur un graphique. Cependant, un changement très petit à l'algorithme produit un autre algorithme qui ne produit efficacement un MST.

Le Manuel de conception algorithme est le meilleur livre que j'ai trouvé réponse des questions comme celle-ci.

Answer 2

La réponse est non. Pour voir pourquoi, nous allons d'abord articuler la question comme ceci:

Q: Avec une connexion, non orienté, graphique pondéré G = (V, E, w) avec des poids de bord seulement non négatifs, ne le sous-graphe précédent produit par l'algorithme de Dijkstra former un arbre de recouvrement minimal de G

?

(Notez que les graphes non orientés sont une classe spéciale de graphes orientés, il est donc parfaitement autorisé à utiliser l'algorithme de Dijkstra sur les graphes non orientés. En outre, le MST de ne sont définis que pour connectés, les graphes non orientés et sont insignifiants si le graphique est pas pondéré , donc nous devons limiter notre demande à ces graphiques.)

A: l'algorithme de Dijkstra à chaque étape sélectionne avidement le bord suivant qui est le plus proche de certains vertex source s . Il fait jusqu'à ce que s est connecté à tous les autres sommets dans le graphe. Il est clair que le sous-graphe précédent qui est produit est un arbre de recouvrement de G, mais est la somme des poids des arêtes minimisée?

algorithme de Prim , qui est connu pour produire un arbre de recouvrement minimal, est très similaire à l'algorithme de Dijkstra, mais à chaque étape il sélectionne avidement le prochain bord qui est le plus proche de chaque sommet a dans le MST de travail à ce stade . Utilisons cette observation pour produire un contre-exemple.

Contre-exemple: Considérons le graphe non orienté G = (V, E, w) où

V = { a, b, c, d }

E = { (a,b), (a,c), (a,d), (b,d), (c,d) }

w = { ( (a,b) , 5 ) ( (a,c) , 5 ) ( (a,d) , 5 ) ( (b,d) , 1 ) ( (c,d) , 1 ) }

Prenez a comme le sommet source.

L'algorithme de Dijkstra prend bords { (a,b), (a,c), (a,d) }.
Ainsi, le poids total de cet arbre couvrant 5 + 5 + 5 = 15 .

L'algorithme de Prim prend bords { (a,d), (b,d), (c,d) }.
Ainsi, le poids total de cet arbre de recouvrement est 5 + 1 + 1 = 7 .

Answer 3

algorithme de Prim utilise le même principe sous-jacent que l'algorithme de Dijkstra.

Answer 4

Je garde un algorithme glouton tel que celui Prim ou Kruskal de. Je crains Djikstra ce ne sera pas le faire, tout simplement parce qu'il réduit le coût entre des paires de noeuds, et non pour l'arbre entier.

Answer 5

Bien sûr, il est possible d'utiliser Dijkstra pour arbre minimum:

dijsktra(s):
dist[s] = 0;
while (some vertices are unmarked) {
    v = unmarked vertex with 
    smallest dist;
    Mark v; // v leaves “table”
    for (each w adj to v) {
        dist[w] = min[ dist[w], dist[v] + c(v,w) ];
    }
}

Voici un exemple d'utilisation Dijkstra pour spanning tree:

Vous pouvez trouver d'autres explications dans les fondations du livre algorithmes, chapitre 4, section 2.

Hope this help