Minimaler Spannbaum vs kürzester Pfad

Was ist der Unterschied zwischen dem Minimum-Spanning-Tree-Algorithmus und einem Shortest-Path-Algorithmus?

In meiner Datenstrukturklasse haben wir zwei Minimum-Spanning-Tree-Algorithmen (Prim und Kruskal) und einen Shortest-Path-Algorithmus (Dijkstra) behandelt.

Der minimale Spannbaum ist ein Baum in einem Diagramm, der alle Eckpunkte überspannt, und das Gesamtgewicht eines Baums ist minimal. Der kürzeste Weg ist ziemlich offensichtlich, es ist ein kürzester Weg von einem Scheitelpunkt zum anderen.

Was ich nicht verstehe, ist, dass der minimale Spannbaum ein minimales Gesamtgewicht hat. Wären die Pfade im Baum nicht die kürzesten? Kann jemand erklären, was ich vermisse?

Jede Hilfe wird geschätzt.

Betrachten Sie das Dreieckdiagramm mit den Einheitsgewichten - es hat drei Eckpunkte und alle drei Kanten haben das Gewicht . Der kürzeste Weg zwischen zwei Scheitelpunkten ist der direkte Weg. Wenn Sie jedoch alle Scheitelpunkte zusammenfassen, erhalten Sie eher ein Dreieck als einen Baum. Jede Sammlung von zwei Kanten bildet einen minimalen Spannbaum in diesem Diagramm. Wenn Sie jedoch (zum Beispiel) auswählen , verpassen Sie den kürzesten Pfad .$x,y,z$$\{x,y\},\{x,z\},\{y,z\}$$1$$\{x,y\},\{y,z\}$$\{x,z\}$

Fazit: Wenn Sie alle kürzesten Wege zusammenfassen, erhalten Sie nicht unbedingt einen Baum.

Sie haben Recht, dass die beiden Algorithmen von Dijkstra (kürzeste Wege von einem einzelnen Startknoten) und Prim (minimales Gewicht über Baum ab einem bestimmten Knoten) eine sehr ähnliche Struktur haben. Sie sind beide gierig (nehmen aus heutiger Sicht die beste Kante) und bauen einen Baum, der sich über den Graphen erstreckt.

Der von ihnen minimierte Wert ist jedoch unterschiedlich. Dijkstra wählt als nächste Kante diejenige aus, die vom Baum zu einem Knoten führt, der dem Startknoten noch nicht am nächsten liegt. (Dann werden mit dieser Auswahl die Entfernungen neu berechnet.) Prim wählt als Kante die kürzeste, die aus dem bisher konstruierten Baum herausführt. Daher wählten beide Algorithmen eine "minimale Kante". Der Hauptunterschied ist der als minimal gewählte Wert. Für Dijkstra ist es die Länge des vollständigen Pfades vom Startknoten zum Kandidatenknoten, für Prim ist es nur das Gewicht dieser einzelnen Kante.

Um den Unterschied zu erkennen, sollten Sie versuchen, einige Beispiele zu konstruieren, um zu sehen, was passiert. Das ist wirklich lehrreich. Das einfachste Beispiel, das ein anderes Verhalten zeigt, ist ein Dreieck mit Kanten und der Länge 2, während die Länge 1 hat Dijkstra wählt und (gibt zwei Pfade der Länge 2 an), während Prim und auswählt (gibt den Spanning Tree von Gewicht 3).$x,y,z$$\{x,y\}$$\{x,z\}$$\{y,z\}$$x$$\{x,y\}$$\{x,z\}$$\{x,y\}$$\{y,z\}$

Bei Kruskal ist das etwas anders. Es löst den minimalen Spannbaum, wählt aber während der Ausführung eine Kante, die möglicherweise keinen Baum bildet, und vermeidet lediglich Zyklen. So können die Teillösungen getrennt werden. Am Ende bekommst du einen Baum.

Obwohl die Berechnungen für Minimum Spanning Tree- und Shortest Path-Algorithmen ähnlich aussehen, konzentrieren sie sich auf zwei unterschiedliche Anforderungen.

In MST muss jeder Scheitelpunkt einmal erreicht werden (Diagrammbaum erstellen), und die Gesamtkosten (kollektiv) für das Erreichen jedes Scheitelpunkts müssen unter allen möglichen Kombinationen minimal sein.

Bei Shortest Path ist es erforderlich, den Zielscheitelpunkt vom Quellscheitelpunkt mit möglichst geringen Kosten (kürzestes Gewicht) zu erreichen. Hier müssen wir uns also nicht darum kümmern, jeden Scheitelpunkt zu erreichen, sondern uns nur auf die Quell- und Zielscheitelpunkte zu konzentrieren, und genau hier liegt der Unterschied.

Hier ist das Beispiel, um zu verdeutlichen, warum MST nicht unbedingt den kürzesten Pfad zwischen zwei Scheitelpunkten ergibt.

(A)----5---(B)----5---(C)
 |                     |
 |----------7----------| 

Im MST-Fall Kanten AB. BC wird auf MST mit einem Gesamtgewicht von 10 sein. Die Kosten für das Erreichen von A bis C in MST betragen 10.

Im Fall des kürzesten Pfads ist der kürzeste Pfad zwischen A und C AC, der 7 ist. AC war nie in der MST.

Der Unterschied liegt im eigentlichen Ziel dieses Algorithmus.

Dijkstra's - Hier ist das Ziel, von Anfang bis Ende zu erreichen. Sie kümmern sich nur um diese 2 Punkte und optimieren Ihren Weg entsprechend.

Krusal's - Hier können Sie von jedem Punkt aus beginnen und müssen alle anderen Punkte in der Grafik besuchen. Sie müssen also nicht immer den kürzesten Weg für zwei beliebige Punkte wählen. Stattdessen liegt der Fokus auf der Auswahl des Pfades, der Sie zu einem kürzeren Pfad für alle anderen Punkte führt.

Ich denke, ein Beispiel wird es klarer machen.

Der Spannbaum sieht aus wie unten. Dies liegt daran, dass wir, wenn wir die Kanten in dieser Konfiguration addieren, die geringstmöglichen Gesamtkosten erhalten : 2 + 5 + 14 + 4 = 25.

(1)   (4)
  \   /
   (2)
  /   \
(3)   (5)

Wenn Sie auf den Baum blicken, denken Sie möglicherweise fälschlicherweise, dass er Ihnen die kürzesten Wege bietet, aber in der Praxis ist dies nicht der Fall. Ein Beispiel: Wenn wir von einem Knoten (1)zu einem anderen wechseln wollten, (4)würden wir uns 7 kosten. Wenn wir jedoch den Dijkstra-Algorithmus in der ursprünglichen Grafik verwenden würden, würden wir feststellen, dass wir mit Kosten von direkt von einem Knoten (1)zum nächsten wechseln können .(4)5

Praktisches Beispiel, um den Unterschied zu zeigen>

Angenommen, Sie reisen mit dem Zug in einer Stadt an und möchten zu Ihrem Hotel gelangen.

Option 1: Ein Taxi nehmen: Das Taxi nimmt den kürzesten Weg von der Station zu Ihrem Hotel. Wenn der Fahrer einem Pfad entlang des Baums mit dem kürzesten Pfad in der Mitte der Station folgen soll.

Option 2: Nehmen Sie einen Bus. Das Busunternehmen möchte nicht nur Sie, sondern auch viele andere Menschen bedienen. Der ideale Weg würde alle wichtigen Punkte der Stadt einschließen. Es folgt also (*) einem Pfad entlang des minimalen Spannbaums. Deshalb ist der Bus langsamer, aber wenn die Kosten geteilt werden, ist er billiger.

(*) Tatsächlich würden sich die Leute beschweren, wenn der minimale Spannbaum verwendet würde (die Busfahrt wäre zu lang). In der Praxis wäre es also eine gemischte Lösung und würde einen Alpha-Baum verwenden (auf halbem Weg zwischen einem minimalen Spannbaum und einem Baum mit dem kürzesten Pfad).

Sie basieren auf zwei unterschiedlichen Eigenschaften. Der minimale Spannbaum basiert auf der Eigenschaft cut, während der kürzeste Pfad auf der Eigenschaft edge relaxing basiert.

Ein Schnitt teilt ein Diagramm in zwei Komponenten. Es können mehrere Kanten beteiligt sein. In MST wählen wir die Kante mit dem geringsten Gewicht aus.

Kantenrelaxation besagt, dass ich bei bekanntem Abstand zwischen A und B: dist (a, b) und dist zwischen A und C: dist (a, c), wenn dist (a, b) + Kante (b, c) kleiner ist als dist (a, c), dann kann ich edge (ac) entspannen. Nachdem wir alle Kanten entspannt haben, erhalten wir den kürzesten Weg.

Ich empfehle dringend, das Video über Graph- Algorithmen von Professor Robert Sedgewick anzuschauen .