Können wir Dijkstras Algorithmus ändern, um mit negativen Gewichten zu arbeiten?

Dijkstra kann es sich leisten, jeden Knoten einmal zu besuchen, denn wenn er einen neuen Knoten auswählt, wählt er den nicht besuchten Knoten, der den kürzesten Pfad von der Wurzel hat. Als Konsequenz kann er davon ausgehen, dass es keinen kürzeren Weg zu diesem Knoten durch einen anderen, nicht besuchten Knoten gibt (denn wenn der beste Weg von A nach B 2 kostet und der beste Weg von A nach C 3 kostet, es gibt keine Chance, einen besseren Weg von A nach B zu finden, wie A & gt; C & gt; B).

Wenn Sie negative Gewichtungen hinzufügen, brechen Sie plötzlich diese Annahme.

Sie könnten natürlich Ihre vorgeschlagene Änderung verwenden, aber dann würden Sie den Vorteil verlieren, jeden Knoten nur einmal zu besuchen; und damit würde es seinen Leistungsgewinn im Vergleich zu anderen Algorithmen wie Ford-Bellman

Sie können den Dijkstra-Algorithmus funktionieren mit negativen Werten versehen, indem Sie einfach sicherstellen, dass Sie keinen Knoten oder eine Kante zweimal durchlaufen. Hier, durch Arbeit , meine ich terminieren. Das Ergebnis ist jedoch möglicherweise nicht optimal.

Dijkstras Algorithmus hat einen gierigen Sinn. Stellen Sie sich die folgende Grafik vor:

Wenn wir von A nach B gehen wollen, wäre der beste Pfad A-C-D-B, aber Dijkstras Algorithmus findet A-B. Du kannst den Dijkstra-Algorithmus nicht zur Vorhersage der Zukunft machen, weil es ein Greedy-Algorithmus ist. Durch die Zukunft vorhersagen meine ich, dass später die Kosten eines Pfades reduziert werden können. Beachten Sie, dass dies bedeutet, dass Ihre Änderung falsch funktioniert, wenn sie auf eine Version von Dijkstras Algorithmus angewendet wird, die endet, sobald das Ziel erkannt wird. In der von Ihnen geposteten Version funktioniert Ihre Änderung, außer dass es effizientere Möglichkeiten gibt, negative Kanten zu behandeln (siehe Kommentare).

Als Randnotiz ist der kürzeste Weg in ungerichteten Graphen mit negativen Werten oder gerichteten Graphen mit negativen Schleifen nicht einmal sinnvoll!

Sie haben grundsätzlich zwei Möglichkeiten.

1. Sie können den Algorithmus wie gewünscht ändern. Wenn Sie einen Graphen ohne negativen Zyklus geleitet haben, dann ist dies ein korrekter Algorithmus, aber er kann sehr langsam sein (weil Sie jeden Knoten viele Male besuchen). Ich denke, dass es einen Fall gibt, wenn dieser Algorithmus exponentielle Zeitkomplexität hat.

2. Sie können die Kantenkosten ändern, indem Sie Potentiale verwenden. Jede Ecke hat ein Potential h (v) und ein Gewicht für die Kante u- & gt; v wird w (u, v) + h (u) - h (v) sein. Beachten Sie, dass dies keinen Einfluss darauf hat, welcher Pfad zwischen gegebenen zwei Vertices (s, t) der kürzeste ist, nur dessen Kosten werden durch h (s) - h (t) geändert. Aber Sie müssen Potenziale berechnen. Gute Methode, dies zu tun, ist hier vorgeschlagen: Ссылка

Nein, nicht möglich wie angegeben. Der Algorithmus macht Sinn nicht mit negativen Wertigkeiten, es sei denn, Sie beschränken den bereitgestellten Grafiktyp erheblich.

Nehmen Sie einen Graphen mit den Knoten A, B, C und Kanten mit den Gewichten AB = -1, BA = 0, BC = 1 an.

Es gibt jetzt keinen kürzesten Weg zwischen A und C mehr und du könntest immer einen kürzeren Weg machen, indem du zwischen A und B noch einmal hin und her gehst.

Der Algorithmus wird natürlich immer noch ausgeführt, aber es gibt falsche Antworten .

Ja, Ihre Änderung würde unter zwei Annahmen funktionieren, die Sie nicht erwähnt haben, aber ich vermutete, dass sie implizit waren:

1. Kürzeste Pfade müssen in Ihrem Eingabediagramm definiert werden. Wenn Sie die Einschränkung für nicht-negative Gewichtungen ablehnen, müssen Sie zumindest verlangen, dass es keine Zyklen mit negativem Gewicht gibt.
2. Die Operation "savee-key v in Q" in Zeile 19 ist für Knoten v, die nicht in Q sind, nicht wirklich sinnvoll. Sie können sie jedoch natürlich mit dem neuen Wert zu Q hinzufügen.

Sie würden jedoch eine wichtige Eigenschaft des Dijkstra-Algorithmus verlieren: Seine gute asymptotische Leistung im schlimmsten Fall. Das Dijkstra von der Stange garantiert eine gute Leistung, da es jeden Knoten und jede Kante höchstens einmal besucht. Mit Ihrer Änderung können Knoten, die bereits entfernt wurden, wieder zur Prioritätswarteschlange hinzugefügt werden, und möglicherweise müssen große Teile des Diagramms immer wieder aufgerufen werden. Im schlimmsten Fall müssen Sie so viele Entspannungen durchführen wie beispielsweise der Bellman-Ford-Algorithmus, aber Sie haben den zusätzlichen Overhead der Prioritätswarteschlange. Das macht Ihre Worst-Case-Leistung schlechter als Bellman-Ford, die daher für Graphen mit negativen Kanten bevorzugt wird.

Dies bedeutet nicht, dass Ihr modifiziertes Dijkstra nicht nützlich ist. Es kann viel besser als Bellman-Ford arbeiten, wenn Sie sehr wenige negative Kanten haben und / oder wenn diese negativen Kanten vom Rest des Graphen durch teure Pfade getrennt sind. Aber sei auf eine ziemlich schlimme Worst-Case-Performance vorbereitet.

Nun, um die bereits besuchten Knoten in der modifizierten Version von Dijkstra einfach zu entspannen, ist das nicht genug (und es würde Ihnen eine falsche Antwort in einem Diagramm mit negativen Kanten geben). Darüber hinaus müssen Sie JEDEN entspannten Rand in Ihren Container legen (zum Beispiel die Prioritätswarteschlange oder nur die Warteschlange). Daher könnten Sie Code aus der Zeile 19 wie folgt überarbeiten:

In diesem Fall könnte Ihr Algorithmus funktionieren. Außerdem wird die Effizienz für die modifizierte Dijkstra-Version für einen positiv gewichteten Graphen nicht abnehmen. Dies könnte leicht bewiesen werden, da dies natürlich ein Greedy-Algorithmus ist.

Für Graphen, die negative Kanten enthalten, könnte der neue Algorithmus im Hinblick auf die theoretische Analyse jedoch langsam werden, aber er wird in der Praxis gut funktionieren.

Tatsächlich könnte man sich einen Algorithmus ansehen, der von Dingfan Duan in China (1994) veröffentlicht wurde und als SPFA (Shortest Path Faster Algorithm) bezeichnet wird. Viele OIer (Olympic of Info) wissen, dass dieser Algorithmus manchmal Dijkstra schlagen könnte.