Unterschied zwischen den Algorithmen von Prim und Dijkstra?

Was ist der genaue Unterschied zwischen den Algorithmen von Dijkstra und Prim? Ich weiß, dass Prims eine MST geben wird, aber der von Dijkstra erzeugte Baum wird auch eine MST sein. Was ist dann der genaue Unterschied?

Der Algorithmus von Prim erstellt einen minimalen Spannbaum für das Diagramm. Dieser Baum verbindet alle Knoten im Diagramm und hat die geringsten Gesamtkosten unter allen Bäumen, die alle Knoten verbinden. Die Länge eines Pfades zwischen zwei beliebigen Knoten im MST ist jedoch möglicherweise nicht der kürzeste Pfad zwischen diesen beiden Knoten im ursprünglichen Diagramm. MSTs sind beispielsweise nützlich, wenn Sie die Knoten im Diagramm physisch verkabeln möchten, um sie mit den geringsten Gesamtkosten mit Strom zu versorgen. Es spielt keine Rolle, dass die Pfadlänge zwischen zwei Knoten möglicherweise nicht optimal ist, da Sie sich nur um die Tatsache kümmern, dass sie verbunden sind.

Der Dijkstra-Algorithmus erstellt einen Baum mit dem kürzesten Pfad ausgehend von einem Quellknoten. Ein kürzester Pfadbaum ist ein Baum, der alle Knoten im Diagramm wieder mit dem Quellknoten verbindet und die Eigenschaft hat, dass die Länge eines Pfads vom Quellknoten zu einem anderen Knoten im Diagramm minimiert wird. Dies ist beispielsweise nützlich, wenn Sie ein Straßennetz aufbauen möchten, das es jedem so effizient wie möglich macht, zu einem wichtigen Wahrzeichen zu gelangen. Es wird jedoch nicht garantiert, dass der Baum mit dem kürzesten Pfad ein minimaler Spannbaum ist, und die Summe der Kosten an den Rändern eines Baums mit dem kürzesten Pfad kann viel höher sein als die Kosten eines MST.

Ein weiterer wichtiger Unterschied betrifft die Art der Diagramme, mit denen die Algorithmen arbeiten. Der Algorithmus von Prim funktioniert nur mit ungerichteten Graphen, da das Konzept eines MST davon ausgeht, dass Graphen von Natur aus ungerichtet sind. (Es gibt so etwas wie eine "minimale überspannende Arboreszenz" für gerichtete Graphen, aber Algorithmen, um sie zu finden, sind viel komplizierter). Der Dijkstra-Algorithmus funktioniert gut bei gerichteten Graphen, da Bäume mit kürzesten Pfaden tatsächlich gerichtet werden können. Darüber hinaus liefert der Dijkstra-Algorithmus nicht unbedingt die richtige Lösung in Diagrammen mit negativen Kantengewichten , während der Prim-Algorithmus damit umgehen kann.

Hoffe das hilft!

Der Dijkstra-Algorithmus erstellt kein MST, sondern findet den kürzesten Weg.

Betrachten Sie dieses Diagramm

       5     5
  s *-----*-----* t
     \         /
       -------
         9

Der kürzeste Weg ist 9, während der MST bei 10 ein anderer "Weg" ist.

Prim- und Dijkstra-Algorithmen sind bis auf die "Relax-Funktion" nahezu identisch.

Prim:

MST-PRIM (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v)    <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

Dijkstra:

Dijkstra (G, w, r) {
    for each key ∈ G.V
        u.key = ∞
        u.parent = NIL
    r.key = 0
    Q = G.V

    while (Q ≠ ø)
        u = Extract-Min(Q)
        for each v ∈ G.Adj[u]
            if (v ∈ Q)
                alt = w(u,v) + u.key  <== relax function, Pay attention here
                if alt < v.key
                    v.parent = u
                    v.key = alt
}

Der einzige Unterschied wird durch den Pfeil hervorgehoben, der die Relax-Funktion ist.

• Der Prim, der nach dem minimalen Spannbaum sucht, kümmert sich nur um das Minimum der Gesamtkanten, die alle Eckpunkte abdecken. Die Relax-Funktion istalt = w(u,v)
• Die Dijkstra, die nach der minimalen Pfadlänge sucht, kümmert sich also um die Kantenakkumulation. Die Relax-Funktion istalt = w(u,v) + u.key

Der Dijsktra-Algorithmus ermittelt den Mindestabstand zwischen Knoten i und allen Knoten (Sie geben i an). Im Gegenzug erhalten Sie den Mindestabstandsbaum vom Knoten i.

Mit dem Prims-Algorithmus erhalten Sie den minimalen Spanning Tree für ein bestimmtes Diagramm . Ein Baum, der alle Knoten verbindet, während die Summe aller Kosten das minimal mögliche ist.

Also mit Dijkstra Sie also mit minimalen Kosten vom ausgewählten Knoten zu einem anderen wechseln. Mit Prims erhalten Sie dies nicht

Der einzige Unterschied, den ich sehe, besteht darin, dass der Prim-Algorithmus einen minimalen Kostenvorteil speichert, während der Dijkstra-Algorithmus die Gesamtkosten von einem Quellscheitelpunkt zum aktuellen Scheitelpunkt speichert.

Dijkstra bietet Ihnen einen Weg vom Quellknoten zum Zielknoten, sodass die Kosten minimal sind. Mit dem Prim-Algorithmus erhalten Sie jedoch einen minimalen Spanning Tree, sodass alle Knoten verbunden sind und die Gesamtkosten minimal sind.

In einfachen Worten:

Wenn Sie also einen Zug einsetzen möchten, um mehrere Städte zu verbinden, würden Sie Prims Algo verwenden. Wenn Sie jedoch so viel Zeit wie möglich von einer Stadt in eine andere sparen möchten, verwenden Sie Dijkstras Algo.

Beide können mit genau demselben generischen Algorithmus wie folgt implementiert werden:

Inputs:
  G: Graph
  s: Starting vertex (any for Prim, source for Dijkstra)
  f: a function that takes vertices u and v, returns a number

Generic(G, s, f)
    Q = Enqueue all V with key = infinity, parent = null
    s.key = 0
    While Q is not empty
        u = dequeue Q
        For each v in adj(u)
            if v is in Q and v.key > f(u,v)
                v.key = f(u,v)
                v.parent = u

Für Prim pass f = w(u, v)und für Dijkstra pass f = u.key + w(u, v).

Eine andere interessante Sache ist, dass Generic oben auch Breadth First Search (BFS) implementieren kann, obwohl dies übertrieben wäre, da eine teure Prioritätswarteschlange nicht wirklich erforderlich ist. Um den generischen Algorithmus in BFS umzuwandeln, übergeben Sie, f = u.key + 1was dem Erzwingen aller Gewichte auf 1 entspricht (dh BFS gibt die minimale Anzahl von Kanten an, die zum Durchlaufen von Punkt A nach B erforderlich sind).

Intuition

Hier ist eine gute Möglichkeit, über den obigen generischen Algorithmus nachzudenken: Wir beginnen mit zwei Buckets A und B. Setzen Sie zunächst alle Ihre Scheitelpunkte in B, sodass der Bucket A leer ist. Dann verschieben wir einen Scheitelpunkt von B nach A. Betrachten Sie nun alle Kanten von Scheitelpunkten in A, die zu den Scheitelpunkten in B übergehen. Wir haben die eine Kante anhand einiger Kriterien aus diesen Überkreuzungskanten ausgewählt und den entsprechenden Scheitelpunkt von B nach A verschoben A. Wiederholen Sie diesen Vorgang, bis B leer ist.

Eine Brute-Force-Methode zur Umsetzung dieser Idee wäre die Aufrechterhaltung einer Prioritätswarteschlange der Kanten für die Scheitelpunkte in A, die zu B übergeht. Dies wäre natürlich problematisch, wenn der Graph nicht dünn wäre. Die Frage wäre also, ob wir stattdessen die Prioritätswarteschlange der Eckpunkte beibehalten können. Dies in der Tat können wir als unsere Entscheidung schließlich ist, welchen Scheitelpunkt wir aus B auswählen sollen.

Historischer Zusammenhang

Es ist interessant, dass die generische Version der Technik hinter beiden Algorithmen konzeptionell so alt ist wie 1930, selbst wenn es keine elektronischen Computer gab.

Die Geschichte beginnt mit Otakar Borůvka, der einen Algorithmus für einen Freund seiner Familie benötigte, um herauszufinden, wie Städte im Land Mähren (heute Teil der Tschechischen Republik) mit kostengünstigen Stromleitungen verbunden werden können. Er veröffentlichte seinen Algorithmus 1926 in einer mathematikbezogenen Zeitschrift, da es damals keine Informatik gab. Dies machte Vojtěch Jarník auf sich aufmerksam, der über eine Verbesserung des Borůvka-Algorithmus nachdachte und ihn 1930 veröffentlichte. Tatsächlich entdeckte er denselben Algorithmus, den wir heute als Prims Algorithmus kennen, der ihn 1957 wieder entdeckte.

Unabhängig davon musste Dijkstra 1956 ein Programm schreiben, um die Fähigkeiten eines neuen Computers zu demonstrieren, den sein Institut entwickelt hatte. Er fand es cool, wenn der Computer Verbindungen findet, um zwischen zwei Städten der Niederlande zu reisen. Er entwarf den Algorithmus in 20 Minuten. Er erstellte ein Diagramm von 64 Städten mit einigen Vereinfachungen (da sein Computer 6-Bit war) und schrieb Code für diesen Computer von 1956. Er hat seinen Algorithmus jedoch nicht veröffentlicht, da es in erster Linie keine Fachzeitschriften für Informatik gab und er der Meinung war, dass dies möglicherweise nicht sehr wichtig ist. Im nächsten Jahr lernte er das Problem kennen, Klemmen neuer Computer so anzuschließen, dass die Länge der Drähte minimiert wurde. Er dachte über dieses Problem nach und entdeckte Jarník / Prim 'wieder. s Algorithmus, der wieder dieselbe Technik verwendet wie der Algorithmus mit dem kürzesten Pfad, den er ein Jahr zuvor entdeckt hatte. Ererwähnte, dass beide seiner Algorithmen ohne Verwendung von Stift oder Papier entworfen wurden. Im Jahr 1959 veröffentlichte er beiden Algorithmen in einem Papier , das nur 2 und eine halbe Seite lang ist.

Dijkstra findet den kürzesten Weg zwischen seinem Anfangsknoten und jedem anderen Knoten. Im Gegenzug erhalten Sie den Mindestabstandsbaum vom Anfangsknoten, dh Sie können jeden anderen Knoten so effizient wie möglich erreichen.

Mit dem Prims-Algorithmus erhalten Sie die MST für einen bestimmten Graphen, dh einen Baum, der alle Knoten verbindet, während die Summe aller Kosten das minimal mögliche ist.

Um eine Geschichte mit einem realistischen Beispiel kurz zu machen:

1. Dijkstra möchte den kürzesten Weg zu jedem Zielpunkt kennen, indem er Reisezeit und Kraftstoff spart.
2. Prim möchte wissen, wie ein Zugschienensystem effizient eingesetzt werden kann, um Materialkosten zu sparen.

Direkt aus dem Wikipedia-Artikel von Dijkstra's Algorithm :

Der Prozess, der dem Dijkstra-Algorithmus zugrunde liegt, ähnelt dem gierigen Prozess, der im Prim-Algorithmus verwendet wird. Prims Zweck ist es, einen minimalen Spannbaum zu finden, der alle Knoten im Diagramm verbindet. Dijkstra befasst sich nur mit zwei Knoten. Prims wertet nicht das Gesamtgewicht des Pfads vom Startknoten aus, sondern nur den einzelnen Pfad.

Ich hatte in letzter Zeit die gleiche Frage und ich denke, ich könnte mein Verständnis teilen ...

Ich denke, der Hauptunterschied zwischen diesen beiden Algorithmen (Dijkstra und Prim) liegt in dem Problem, das sie lösen sollen, nämlich dem kürzesten Weg zwischen zwei Knoten und dem minimalen Spanning Tree (MST). Die formale Aufgabe besteht darin, den kürzesten Weg zwischen beispielsweise Knoten s und t zu finden , und eine rationale Anforderung besteht darin, jede Kante des Graphen höchstens einmal zu besuchen. Es ist jedoch NICHT erforderlich, dass wir den gesamten Knoten besuchen. Letzteres (MST) soll uns ALLE besuchen lassen Knoten (höchstens einmal) zu , und mit der gleichen rationalen Anforderung, jede Kante höchstens einmal zu besuchen.

Abgesehen davon erlaubt uns Dijkstra, eine Abkürzung zu nehmen, so lange ich von s nach t komme , ohne mir die Konsequenz Sorgen zu machen - sobald ich zu t komme , bin ich fertig! Zwar gibt es auch einen Weg von ist s bis t in den MST, aber der s - t Weg ist mit Erwägungen aller übrigen Knoten erstellt, daher kann dieser Weg länger als die s - t Pfad durch den Dijstra Algorithmus gefunden. Unten ist ein kurzes Beispiel mit 3 Knoten:

                                  2       2  
                          (s) o ----- o ----- o (t)     
                              |               |
                              -----------------
                                      3

Nehmen wir an, jede der oberen Kanten kostet 2 und die untere Kante 3, dann sagt uns Dijktra, dass wir den unteren Pfad nehmen sollen, da uns der mittlere Knoten egal ist. Auf der anderen Seite gibt Prim uns eine MST mit den oberen 2 Kanten zurück und verwirft die untere Kante.

Dieser Unterschied spiegelt sich auch in dem subtilen Unterschied in den Implementierungen wider: Im Dijkstra-Algorithmus muss ein Buchhaltungsschritt (für jeden Knoten) durchgeführt werden, um den kürzesten Pfad von s nach dem Absorbieren eines neuen Knotens zu aktualisieren , während im Prim-Algorithmus dort ist keine solche Notwendigkeit.

Der Hauptunterschied zwischen den grundlegenden Algorithmen liegt in ihren unterschiedlichen Kantenauswahlkriterien. Im Allgemeinen verwenden beide eine Prioritätswarteschlange für die Auswahl der nächsten Knoten, haben jedoch unterschiedliche Kriterien für die Auswahl der benachbarten Knoten der aktuellen Verarbeitungsknoten: Der Prim-Algorithmus erfordert, dass die nächsten benachbarten Knoten ebenfalls in der Warteschlange bleiben, während der Dijkstra-Algorithmus dies nicht tut:

def dijkstra(g, s):
    q <- make_priority_queue(VERTEX.distance)
    for each vertex v in g.vertex:
        v.distance <- infinite
        v.predecessor ~> nil
        q.add(v)
    s.distance <- 0
    while not q.is_empty:
        u <- q.extract_min()
        for each adjacent vertex v of u:
            ...

def prim(g, s):
    q <- make_priority_queue(VERTEX.distance)
    for each vertex v in g.vertex:
        v.distance <- infinite
        v.predecessor ~> nil
        q.add(v)
    s.distance <- 0
    while not q.is_empty:
        u <- q.extract_min()
        for each adjacent vertex v of u:
            if v in q and weight(u, v) < v.distance:// <-------selection--------
            ...

Die Berechnungen von vertex.distance sind der zweite unterschiedliche Punkt.

Der Dijkstra-Algorithmus ist ein Problem mit dem kürzesten Pfad aus einer Quelle zwischen Knoten i und j, aber der Prim-Algorithmus ist ein minimales Spanning Tree-Problem. Diese Algorithmen verwenden ein Programmierkonzept namens "Greedy Algorithmus".

Wenn Sie diese Vorstellung überprüfen, besuchen Sie bitte

1. Gieriger Algorithmus Vorlesungsnotiz: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/07-greedy.pdf
2. Minimaler Spanning Tree: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/20-mst.pdf
3. Kürzester Pfad aus einer Hand: http://jeffe.cs.illinois.edu/teaching/algorithms/notes/21-sssp.pdf

Dijkstras-Algorithmus wird nur verwendet, um den kürzesten Weg zu finden.

Im Minimum Spanning Tree ( Prim- oder Kruskal-Algorithmus) erhalten Sie minimale Egdes mit minimalem Kantenwert.

Zum Beispiel: - Stellen Sie sich eine Situation vor, in der Sie kein großes Netzwerk erstellen möchten, für das Sie eine große Anzahl von Drähten benötigen, damit diese Drahtzählung mit dem Minimum Spanning Tree (Prim- oder Kruskal-Algorithmus) durchgeführt werden kann (dh) Geben Sie eine minimale Anzahl von Kabeln an, um eine große kabelgebundene Netzwerkverbindung mit minimalen Kosten herzustellen.

Während "Dijkstras-Algorithmus" verwendet wird, um den kürzesten Weg zwischen zwei Knoten zu erhalten, während alle Knoten miteinander verbunden werden.

Die einfachste Erklärung ist, dass Sie in Prims nicht den Startknoten angeben , sondern in dijsktra (Sie müssen einen Startknoten haben) den kürzesten Weg vom angegebenen Knoten zu allen anderen Knoten finden müssen.

@templatetypedef hat den Unterschied zwischen MST und dem kürzesten Pfad abgedeckt. Ich habe den Algorithmusunterschied in einem anderen behandelt. Antworten Sie also, indem Sie demonstrieren, dass beide mit demselben generischen Algorithmus implementiert werden können, der einen weiteren Parameter als Eingabe verwendet: Funktion f(u,v). Der Unterschied zwischen dem Algorithmus von Prim und Dijkstra ist einfach der, den f(u,v)Sie verwenden.

Auf Codeebene ist der andere Unterschied die API.

Sie initialisieren Prim mit einem Quellscheitelpunkt, s , dh Prim.new(s); s kann ein beliebiger Scheitelpunkt sein, und unabhängig von s ist das Endergebnis, bei dem es sich um die Kanten des minimalen Spannbaums (MST) handelt, dasselbe. Um die MST-Kanten zu erhalten, rufen wir die Methode aufedges() .

Sie initialisieren Dijkstra mit einer Quelle Vertex, s , das heißt, Dijkstra.new(s)dass Sie kürzesten Weg / Abstand zu allen anderen Ecken erhalten möchten. Das Endergebnis ist der kürzeste Weg / Abstand von s zu allen anderen Eckpunkten. sind je nach s unterschiedlich . Um die kürzesten Wege / Entfernungen Suche von s an jedem Scheitelpunkt, v , rufen wir die Methoden distanceTo(v)und pathTo(v)jeweils.