Warum können wir den Dijkstra-Algorithmus nicht auf ein Diagramm mit negativen Gewichten anwenden?

Question

Warum können wir den Dijkstra-Algorithmus nicht auf ein Diagramm mit negativen Gewichten anwenden?

Answer 1

Was bedeutet es, den billigsten Weg von A nach B zu finden, wenn Sie jedes Mal, wenn Sie von C nach D reisen, bezahlt haben??

Wenn zwischen zwei Knoten ein negatives Gewicht besteht, besteht der "kürzeste Pfad" darin, für immer zwischen diesen beiden Knoten hin- und herzulaufen. Je mehr Hopfen, desto "kürzer" wird der Weg.

Dies hat nichts mit dem Algorithmus zu tun, und alles hat mit der Unmöglichkeit zu tun, eine solche Frage zu beantworten.

bearbeiten:

Die obige Anspruch nimmt an bidirektionale Verbindungen. Wenn es keine Zyklen gibt, die ein insgesamt negatives Gewicht haben, haben Sie keine Möglichkeit, sich für immer zu bewegen und bezahlt zu werden.

In einem solchen Fall Dijkstra-Algorithmus kann noch fehlschlagen:

Betrachten zwei Pfade:

• einen optimalen Weg, die Kosten in Höhe von 100 Racks auf, bevor die letzte Kante überquert, die eine -25 hat Gewicht, insgesamt 75 geben, und
• ein suboptimaler Weg, der nicht negativ gewichtet hat Kanten mit Gesamtkosten von 90.

Dijkstra-Algorithmus wird inves Tigiere den suboptimalen Pfad zuerst und deklariere ihn selbst, wenn er ihn findet. Es wird niemals dem Unterpfad folgen, der schlechter ist als die erste gefundene Lösung

Answer 2

Stellen Sie sich vor, Sie hätten einen gerichteten Graphen mit einem gerichteten Zyklus, und die gesamte "Entfernung" wäre ein negatives Gewicht. Wenn Sie auf Ihrem Weg vom Scheitelpunkt zum Anfang bis zum Ende diesen gerichteten Zyklus durchlaufen könnten, könnten Sie beliebig oft um den gerichteten Zyklus herumgehen.

Und das bedeutet, dass Sie Ihren Weg quer durch den Graph einen unendlich negativen Abstand (oder effektiv so) haben können.

Solange jedoch keine gerichteten Zyklen um Ihren Graphen herum vorhanden sind, können Sie den Algorithmus von Dijkstra verwenden, ohne dass etwas explodiert.

Alles, was gesagt wird, dort, wenn Sie ein Diagramm mit negativen Gewichten haben, könnten Sie den Belman-Ford Algorithmus verwenden. Wegen der Allgemeinheit dieses Algorithmus ist es jedoch etwas langsamer. Der Bellman-Ford-Algorithmus nimmt O (V · E), wobei die Dijkstra-Zeit 0 (E + VlogV) Zeit

Answer 3

Ich gebe Ihnen ein Gegenbeispiel. Betrachten wir folgende Grafik

http://img853.imageshack.us/img853/7318/3fk8.png

Angenommen, Sie in Vertex begonnen A und Sie wollen kürzesten Weg zu D.Dijkstra-Algorithmus tun würde, wie folgt vorgehen: Fetch aus der Warteschlange Vertex mit minimalem Abstand

1. Mark A als besucht und fügt Eckpunkten B und C
2. in der Warteschlange. Es ist B
3. Mark B als besucht und fügt Vertex D in der Warteschlange.
4. Abruf aus der Warteschlange. Nicht ist es Vertex D.
5. Mark D als besuchte

Dijkstra sagt kürzesten Weg A-D hat die Länge 2, aber es ist offensichtlich nicht wahr.