Dijkstra Behandlung eine negative Kante und geben Sie die richtige Lösung, und einmal falsch geben

Question

Ich weiß, dass dies als Duplikat ausgewählt werden kann (seit ich dieses gesehen habe Negative weights using Dijkstra's Algorithm Ich denke, keine der Antworten in SO sind, was ich suche. Ich interessiere mich für die Lösung mit Dijkstra-Algorithmus in Graph, die eine negative Kante hat, aber dass Dijkstra immer noch die richtige Lösung zeigt. Wie würde diese Grafik aussehen? Ich kann mir nicht vorstellen, oder ich bin nicht gut genug, um Dijkstra zu verstehen Negative Kanten überhaupt. Und ich weiß, dass es eine Grafik mit negativer Kante gibt, die mit Dijkstra durchquert werden kann und immer noch den richtigen Weg hat. Bitte nicht, Bellman-Ford oder Johnsons Algorithmus zu verwenden.

Answer 1

In Tatsache ist, Dijkstras Algorithmus versucht, den Kurzschluss zu finden est-Pfad durch den Vergleich von Pfadkosten, die das Ziel erreichen können, und nimmt den Pfad mit den niedrigsten Kosten. Es spart im Grunde die niedrigsten Kosten vom Startpunkt bis zu jedem einzelnen Knoten, der Sie zum Ziel bringen kann. Wenn der negative Wert diese Reihenfolge nicht beeinflusst (die negative Kante ist ein Teil des kürzesten Pfads), gibt es kein Problem mit dem Pfad (aber Sie erhalten den falsche Pfadkosten). Es gibt auch den Fall, dass die negative Kante Sie nicht zum Ziel führen kann (es ist kein Teil eines Pfades), dann haben Sie kein Problem im Pfad und den Kosten. Vielleicht finden Sie ein drittes Beispiel, die Kante ist Teil eines der Pfade, die Sie zum Ziel führt, aber es ist immer noch nicht Teil des kürzesten Pfades. Hoffe, das half, Viel Glück.

Answer 2

Wenn der absolute Wert der negativen Kante kleiner ist als das Gewicht einer anderen Kante im Diagramm, dann funktioniert der Dijkstra-Algorithmus.

Dies stellt sicher, dass wir nicht die Situation haben, dass die Entfernung zu einem Knoten, der aus der Warteschlange herausgefallen ist, später aktualisiert wird. Wie in den typischen Einstellungen (nur positive Gewichte), sobald wir einen Knoten aus der Warteschlange entfernen, sind wir garantiert, dass wir ihn nicht über einen kürzeren Pfad erreichen können.

Hinweis: gilt nicht für gerichtete Graphen, in denen der Quellendpunkt der negativen Flanke gefunden werden kann, nachdem der Zielendpunkt aus der Warteschlange abgerufen wurde (und möglicherweise einen Knoten aktualisieren muss, der gepoppt wurde)).

Answer 3

Beispiel wäre eine Grafik, bei der negative Kanten zu vertikal ohne Kanten führen.