Kann Dijkstras Single Source Shortest Path Algorithmus einen unendlichen Zyklus in einem Graphen erkennen?
So kam ich zu diesem schönen Problem, das Sie auffordert, ein Programm zu schreiben, das feststellt, ob in einem gerichteten Graph ein negativer unendlicher kürzester Pfad existiert. (Man kann sich auch vorstellen, ob ein "negativer Zyklus" im Graphen existiert). Hier ist ein Link für das Problem:
Ich habe das Problem erfolgreich gelöst, indem ich den Bellman Ford Algorithmus zweimal ausgeführt habe, indem ich mit einer beliebigen Quelle in der Grafik begonnen habe. Beim zweiten Mal, wenn ich den Algorithmus starte, überprüfe ich, ob ein Knoten gelockert werden kann. Wenn ja, dann ist definitiv ein negativer Zyklus in der Grafik. Unten ist mein C ++ Code:
%Vor%Ein Professor hat mir einmal gesagt, dass Dijkstras Algorithmus für den kürzesten Weg einen solchen negativen Zyklus nicht finden kann, aber er hat es nicht gerechtfertigt. Ich bezweifle diese Behauptung tatsächlich.
Meine Frage ist, kann Dijktstra's Single Source Shortest Path Algorithmus diesen negativen Zyklus erkennen?
Natürlich kann ich Dijkstra's ausprobieren und prüfen, ob es funktioniert, aber ich war aufgeregt, diese Idee mit Ihnen zu teilen.
2 Antworten
Sie haben Ihren Professor falsch verstanden: Er muss gesagt haben, dass der Dijkstra-Algorithmus nicht funktioniert, wenn im Diagramm ein negativer -Zyklus ist. Positive Zyklen sind erlaubt.
Der Grund, warum der Algorithmus bei Graphen mit negativen Zyklen nicht funktioniert, ist, dass der kürzeste Pfad in solchen Graphen nicht definiert ist: Sobald Sie einen negativen Zyklus erreichen, können Sie die Kosten Ihres "kürzesten Pfades" so niedrig wie gewünscht bringen indem Sie den negativen Zyklus mehrmals verfolgen.
Betrachten Sie das obige Beispiel: Sie beginnen am Vertex Start und erreichen A mit den Kosten von 1 . Dann gehst du zu B mit den Gesamtkosten von -1 , zu C mit der Summe von -4 , und jetzt kannst du zurück zu A mit den Gesamtkosten von Null gehen. Durch Verlängerung der Reihenfolge Start - A - B - C - A - B - C - A - B - C -...- Finish Sie können die Kosten eines Pfades von Start auf Finish auf eine so kleine negative Zahl reduzieren, wie Sie möchten.
Beachten Sie, dass die Einschränkung des negativen Zyklus für alle Algorithmen gilt, um den kürzesten Pfad in einem Graphen zu finden. Die Einschränkung von Dijkstras Algorithmus ist noch stärker: Es verbietet alle negativen Kanten.
Es ist sicherlich möglich, den Algorithmus von Dijkstra zu modifizieren, um negative Zyklen zu erkennen, aber das hat keinen Sinn, weil Sie keine negativen Kanten mehr haben.
Kein Algorithmus weder Dijkstra noch Bellman-Ford noch Floyd-Warshall arbeiten an Graphen mit negativem Zyklus, aber die letzten beiden können einen erkennen, während Dijkstra's nicht kann, weil Dijkstra's gierig ist, während andere dynamische Programmierung verwenden. Darüber hinaus arbeitet Dijkstra nicht mit negativen Gewichtungen, auch ohne negative Zyklen .
Tags und Links algorithm shortest-path infinite bellman-ford dijkstra