Verwendung des Dijkstra-Algorithmus mit negativen Kanten?

  • Die meisten Bücher erklären den Grund, warum der Algorithmus nicht mit negativen Kanten arbeitet, da Knoten nach dem Erreichen des Knotens aus der Prioritätswarteschlange gelöscht werden, da der Algorithmus davon ausgeht, dass die kürzeste Entfernung gefunden wurde. Da jedoch negative Flanken den Abstand verringern können, könnte ein zukünftiger kürzerer Abstand gefunden werden. Da der Knoten jedoch gelöscht wird, kann er nicht aktualisiert werden.

    Wäre es nicht naheliegend, den Knoten nicht zu löschen ? Warum sollte der Knoten nicht in der Warteschlange verbleiben. Wenn eine zukünftige Entfernung kürzer gefunden wird, kann er aktualisiert werden. Wenn ich das Problem falsch verstanden habe, was verhindert , dass der Algorithmus mit negativen Kanten verwendet wird?

    25 June 2012
    Kaveh
3 answers
  • Kurze Antwort ist, dass Dijkstra ein gieriger Algorithmus ist. Das bedeutet, wir nehmen an, dass wir in jedem Schritt des Algorithmus die beste Wahl getroffen haben. Bei negativen Flanken ist dies nicht mehr möglich und daher reicht ein gieriger Algorithmus nicht aus.

    Hier ist eine Analogie: (das kann helfen oder sogar verwirren.) mehr) Nehmen Sie ein konvexes Optimierungsproblem und stecken Sie eine Konkavität hinein. Stellen Sie jetzt die Frage, warum es nicht mit einem linearen Programm gelöst werden kann. Das Problem ist, dass die Prämisse des linearen Programms ist, dass wir, sobald wir die Kante einer konvexen Fläche in Richtung der Optimalität erreichen, sicher sind, dass sie optimal ist. Mit einer Konkavität funktioniert dies nicht mehr und der Algorithmus fällt flach ab. Die negativen Werte sind wie diese Konkavitäten, sie führen zu lokalen Extremen, die das Auffinden der globalen Werte erschweren.

    24 June 2012
    FlySwat
  • Ja, das Löschen des Knotens ist die naheliegende und akzeptierte Lösung für negative Kanten. Der Trick hier ist, dass wir aus irgendeinem historischen Grund und als Teil eines teuflischen Schemas, um Sie besser zu verwirren, für diesen modifizierten Algorithmus einen anderen Namen verwenden *:

    Bellman-Ford-Algorithmus .

    * ok Einige Vorbehalte, aber ich versuche hier nur die Dinge zu beschönigen ...

    Der Bellman-Ford-Algorithmus berechnet kürzeste Pfade aus einer Quelle in einem gewichtetes Digraph Bei Graphen mit nur nicht negativen Kantengewichtungen löst der schnellere Dijkstra-Algorithmus auch das Problem. Daher wird Bellman-Ford in erster Linie für Graphen mit negativen Kantengewichten verwendet. Der Algorithmus ist nach seinen Entwicklern Richard Bellman und Lester Ford, Jr., genannt.

    Wenn ein Graph einen "negativen Zyklus" enthält, dh einen Zyklus, dessen Flanken sich zu einem negativen Wert summieren, können Gänge mit beliebig geringem Gewicht durch wiederholtes Folgen des Zyklus konstruiert werden, so dass dies nicht der Fall ist ein kürzester Weg sein. Bellman-Ford kann negative Zyklen erkennen und deren Existenz melden, kann jedoch keine korrekte Antwort liefern, wenn ein negativer Zyklus von der Quelle aus erreichbar ist. [1]


    Vorsichtsmaßnahmen: Wie von nhahtdh in den Kommentaren ausgeführt, müssen Sie beachten, dass negative Kanten zulässig sind. In diesem Fall kann es unendlich viele negative Schleifen geben, und wenn dies der Fall ist, gibt es möglicherweise keinen Pfad mit minimaler Länge. Wenn jemand keine negativen Kanten für Sie erwähnt, ist dies wahrscheinlich, weil er sich nicht mit dieser Art von Details beschäftigen möchte.

    Auch, wie JeffE in den Kommentaren darauf hinweist, obwohl Der grundlegende "Relaxations" -Schritt ist in beiden Algorithmen derselbe. Die Optimierung mit der Prioritätswarteschlange wird bei negativen Flanken nicht wirklich angewendet und kann sich als Gegenleistung erweisen

    25 June 2012
    Polsonby
  • Eine geringfügige Variante des Dijkstra-Algorithmus arbeitet an einem Graphen mit negativem Gewicht ohne negativen Zyklus (Competitive Programming 2, Steven Halim). Verwenden Sie den Algorithmus Bellman-Ford für einen allgemeinen Graphen (der einen negativen Zyklus enthalten kann) hat eine feste zeitliche Komplexität von O (VE), garantiert jedoch die Beendigung und ermöglicht die Erkennung eines negativen Zyklus (wir erkennen den negativen Zyklus, da der kürzeste Weg in diesem Fall schlecht definiert ist).

    Wir können Knoten im Dijkstra-Algorithmus in 3 Knotentypen kategorisieren: verarbeitete (deren Wert sich niemals ändert), < em> unverarbeitet (hat einen nicht unendlich großen Wert, kann sich jedoch ändern) und unerreicht (dessen Wert unendlich ist, da wir dies nicht getan haben den Knoten erreicht). Im Pseudocode für den Dijkstra-Algorithmus in Wikipedia (Original?) Wird der Relax-Vorgang nie aufgerufen verarbeiteter Knoten.

    Eine Variante des Dijkstra-Algorithmus speichert nur die nicht verarbeiteten Knoten in einer Datenstruktur für die "get-min" - und "update" -Operation und ruft den Knoten zur Verarbeitung auf . Dadurch werden alle Nachbarn des Knotens gelockert und Push / Modifizieren der Knoten, dessen Abstand zur Datenstruktur verbessert wird. Auf diese Weise kann der verarbeitete -Knoten zu einem nicht verarbeiteten -Knoten zurückgesetzt werden, und seine Nachbarn werden erneut aktualisiert, wenn sie herausgenommen werden. Die Methode ist korrekt, da Änderungen am aktuell besten Wert eines Knotens immer propagiert werden.

    Die Komplexität der Variante auf any nicht negativ. Zyklusdiagramm ist im schlimmsten Fall die exponentielle Zeit , da hier eine Neubewertung der Scheitelpunkte möglich ist. Die tatsächliche Laufzeit der Variante ist d

    16 July 2012
    nhahtdh