Ich habe versucht, den Algorithmus von Dikstra auf zyklisch gewichteten Graphen zu verwenden, ohne die Prioritätswarteschlange (Heap) zu verwenden, und es hat funktioniert.
Dann habe ich google gesucht, "warum zur Hölle brauchen wir eine Prioritätswarteschlange, um das zu implementieren?" Als Ergebnis der Suche ging ich durch Wikipedia, wo ich erfuhr, dass die ursprüngliche Implementierung keine Prioritätswarteschlange verwendet und in O (| V | 2) läuft, d. H. V Quadratzeit.
Wenn wir jetzt die Prioritätswarteschlange entfernen und die normale Warteschlange verwenden, ist die Laufzeit linear, d. h. O (V + E).
Bitte jemand schlägt dann warum brauchen wir Priorität Warteschlange?
Ich hatte genau die gleichen Zweifel und fand einen Testfall, bei dem der Algorithmus ohne eine Prioritätswarteschlange nicht funktionieren würde.
Nehmen wir an, ich habe ein Graph-Objekt g , eine Methode addEdge(a,b,w) , die die Kante vom Vertex a zum Vertex b mit dem Gewicht w hinzufügt.
Lassen Sie mich nun das folgende Diagramm definieren: -
%Vor% Sagen wir, unsere Warteschlange enthält die Knoten in der folgenden Reihenfolge: {0,1,2,3 }
Also wird der Knoten 0 zuerst besucht, dann wird der Knoten 1 besucht.
Zu diesem Zeitpunkt wird der Abstand b / w 0 und 3 mit dem Pfad 0->1->3 zu 6 berechnet und 1 wird als besucht markiert.
Nun wird Knoten 2 besucht und dist b / w 0 und 1 wird mit dem Pfad 0->2->1 auf den Wert 3 aktualisiert, aber da Knoten 1 als besucht markiert ist, können Sie die Entfernung b / w 0 und 3 nicht ändern ( Verwenden des optimalen Pfades) ('0- & gt; 2- & gt; 1- & gt; 3) ist 4.
Ihr Algorithmus schlägt also fehl, ohne die priority_queue zu verwenden.
Es meldet dist b / w 0 und 3, 6 zu sein, während es in Wirklichkeit 4 sein sollte.
Nun, hier ist der Code, mit dem ich den Algorithmus implementiert habe: -
%Vor%Wie erwartet, waren die Ergebnisse wie folgt: -
Mit priority_queue
0
3
2
4
Wird jetzt ohne Prioritätswarteschlange verwendet
0
3
2
6
Für Sparse-Graphen, wenn die Implementierung mit binärer Min-Heap-Laufzeit (E * logV) ist, wenn Sie es jedoch mit Fibonacci-Heap implementieren, wäre Laufzeit (VlogV + E).
Wie Moataz Elmasry sagte, das Beste, was Sie erwarten können, ist O (| E | + | V |. | logV |) mit einer fib-Warteschlange. Zumindest wenn es um große Werte geht.
Die Idee dahinter ist, dass Sie für jeden Knoten (Knoten), an dem Sie gerade arbeiten, bereits den kürzesten Weg gefunden haben. Wenn der Scheitelpunkt nicht der kleinste ist (Abstand + Kantengewicht), ist das nicht unbedingt wahr. Dies ermöglicht es Ihnen, den Algorithmus zu stoppen, sobald Sie alle Ecken, die von Ihrem ursprünglichen Scheitelpunkt aus erreichbar sind, (?) Erweitert haben. Wenn Sie den kleinsten Eckpunkt nicht erweitern, ist es nicht garantiert, dass Sie den kürzesten Pfad finden. Daher müssten Sie jeden einzelnen Pfad testen, nicht nur einen. Anstatt also jede Kante auf nur einem Pfad durchlaufen zu müssen, durchquerst du jede Kante auf jedem Pfad.
Ihre Schätzung für O (E + V) ist wahrscheinlich richtig, der Pfad und die Kosten, die Sie auf der anderen Seite ermittelt haben, sind falsch. Wenn ich mich nicht irre, wäre der Pfad nur der kürzeste, wenn zufällig die erste Kante, die du von jedem Eckpunkt kommst, zufällig die kleinste ist.
So ist Dijkstras Algorithmus für den kürzesten Weg ohne eine Warteschlange mit Priorität nur Dijkstra's Pfadalgorithmus;)
Ein Heap ist die beste Wahl für diese Aufgabe, da es O (log (n)) garantiert, um Kanten zu unserer Warteschlange hinzuzufügen und das oberste Element zu entfernen. Jede andere Implementierung der Prioritätswarteschlange würde Opfer bringen, indem sie entweder unsere Warteschlange hinzufügt oder aus ihr entfernt, um an anderer Stelle einen Leistungsschub zu erhalten. Je nachdem, wie spärlich das Diagramm ist, können Sie mit einer anderen Implementierung der Prioritätswarteschlange eine bessere Leistung erzielen, aber im Allgemeinen ist ein Min-Heap am besten geeignet, da er die beiden Werte ausgleicht.
Nicht die größte Quelle, aber: Ссылка
Tags und Links priority-queue dijkstra