Verwenden Dijkstra ist ein Minimum Spanning Tree zu finden?

Question

Dijkstra normalerweise verwendet wird, um die kürzeste Entfernung zwischen zwei Knoten in einem Graphen zu finden. ein Minimum Spanning Tree kann es verwendet werden? Wenn ja, wie?

Edit:. Das ist keine Hausaufgaben, aber ich versuche, eine Frage auf einer alte Prüfung der Praxis zu verstehen

Answer 1

Streng genommen ist die Antwort nein. Dijkstra-Algorithmus findet den kürzesten Weg zwischen zwei Scheitelpunkten auf einem Graphen. Allerdings ist eine sehr kleine Änderung des Algorithmus einen anderen Algorithmus erzeugt, die effizient eine MST erzeugt.

Das Algorithmus Design Manual ist das beste Buch, das ich auf Antwort gefunden habe Fragen wie diese.

Answer 2

Die Antwort ist nein. Um zu sehen, warum lassen Sie uns zuerst zu artikulieren die Frage wie folgt:

Q: für einen angeschlossenen, ungerichtet, gewichtet Graphen G = (V, E, w) mit nur nicht-negativen Kantengewichten, wird der Vorgänger Subgraph von Dijkstra-Algorithmus erzeugte Spannbaum von G ein Minimum bilden

?

(Beachten Sie, dass ungerichtete Graphen eine spezielle Klasse von gerichteten Graphen sind, so ist es völlig in Ordnung ist Dijkstra-Algorithmus auf ungerichtete Graphen zu verwenden. Darüber hinaus sind nur MST definiert verbunden, ungerichtete Graphen, und trivial sind, wenn der Graph nicht gewichtet ist , so müssen wir unsere Anfrage an diesen Graphen beschränken.)

A: Dijkstra-Algorithmus bei jedem Schritt wählt gierig die nächste Flanke, die am nächsten zu einem gewissen source ist Vertex s . Es tut dies, bis s zu jedem anderen Knoten in dem Graphen verbunden ist. Offensichtlich ist die Vorgänger Subgraphen, die produziert wird, ist ein Spannbaum von G, aber ist die Summe der Kantengewichte minimiert?

Algorithmus von Prim , von denen bekannt ist, einen minimalen Spanning-Tree zu erzeugen, ist sehr ähnlich dem Dijkstra-Algorithmus, aber in jeder Stufe wählt gierig die nächste Flanke, die am nächsten zu ist jeder Eckpunkt derzeit in der Arbeits MST in diesem Stadium . Lassen Sie uns verwenden diese Beobachtung ein Gegenbeispiel zu erzeugen.

Counterexample: Betrachten Sie die ungerichteten Graphen G = (V, E, w) wobei

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 ) }

Nehmen Sie a als Quelle Vertex.

Dijkstra-Algorithmus nimmt Kanten { (a,b), (a,c), (a,d) }.
Somit ist das Gesamtgewicht dieses Spanning Tree 5 + 5 + 5 = 15 .

Prim-Algorithmus nimmt Kanten { (a,d), (b,d), (c,d) }.
Somit ist das Gesamtgewicht dieses Spanning Tree 5 + 1 + 1 = 7 .

Answer 3

Prim-Algorithmus verwendet das gleiche Prinzip wie Dijkstra-Algorithmus.

Answer 4

würde ich auf einen Greedy-Algorithmus halten wie Prim oder Kruskals. Ich fürchte Djikstra die nicht tun, einfach weil es die Kosten zwischen Paaren von Knoten minimiert, nicht für den gesamten Baum.

Answer 5

Natürlich Es ist möglich, Dijkstra für minimalen Spannbaum zu verwenden:

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) ];
    }
}

Hier ist ein Beispiel für die Verwendung von Dijkstra für Spanning Tree:

Sie können eine weitere Erklärung finden in Foundations of Algorithms Buch, Kapitel 4, Abschnitt 2.

Hope this help