Gibt es einen gerichteten, verbundenen Graphen mit nur positiven Kantengewichten, gibt es schnellere Algorithmen, um den kürzesten Weg zwischen zwei Scheitelpunkten zu finden, als Dijkstra mit einem Fibonacci-Haufen?
Wikipedia sagt, dass Dijkstra in O (| E | + | V | * log (| V |)) ist (unter Verwendung eines Fibonacci-Heaps).
Ich suche nicht nach Optimierungen, die zum Beispiel die Hälfte der Ausführungszeit ausmachen, sondern Algorithmen, die sich in einer anderen zeitlichen Komplexität befinden (zB von O (n * log n) nach O (n)).
Außerdem würde ich gerne Ihre Meinung zu folgendem Ansatz erfahren:
Beispiel für Punkt 2:
Stellen Sie sich vor, die GCD wäre 1. Dann würde ich die Kante von
transformieren
A --- & gt; B (Kantengewicht 3)
in ein
A- & gt; A '- & gt; A' '- & gt; B (3 mal Kantengewicht 1)
Diese Transformation kostet konstante Zeit und müsste für jede Kante einmal durchgeführt werden. Also erwarte ich, dass dieser Algorithmus in O (| E |) (Transformation) + O (| E | + | V |) (BFS) = O (2 * | E | + | V |) = O (| E | + | V |)
Danke, dass du dir die Zeit genommen hast, meine Frage zu lesen, und ich hoffe, dass du deine Zeit nicht vernachlässigt hast ^^. Einen schönen Tag noch.
Die große Analyse, die Sie für Ihren Algorithmus durchgeführt haben, ist zutiefst fehlerhaft. Angenommen, alle Kanten sind Primzahlen. Die Anzahl der Kanten im neuen Diagramm entspricht der Summe aller Gewichte. Daher ist O(|E| + |V|) des neuen Graphen tatsächlich O(W x |E| + |V|) im ursprünglichen Graphen, der viel größer sein kann als O(|E| + |V| log |V|) .
Gibt es schnellere Algorithmen als Dijkstra?
Ja. Die Frage ist nicht qualifiziert, um in allen Fällen oder sogar in den meisten Fällen eine bessere Leistung zu verlangen. Ein Algorithmus mit besserer Leistung in einem einzigen Fall ist ausreichend, um eine bejahende Antwort zu erhalten.
Trotz der im Allgemeinen größeren Anzahl von Iterationen, die von der Bellman-Ford-Methode über Dijkstra-Methode, in der Praxis kann die Bellman-Ford-Methode sein überlegen wegen des kleineren Overheads pro Iteration [Golden, B., 1976. "Kürzeste Pfadalgorithmen: Ein Vergleich", Operations Research, Vol. 44, pp. 1164-1168].
Das obige Zitat stammt von Dimitri P. Bertsekas (März 1992). "Ein einfacher und schneller Label-Korrektur-Algorithmus für kürzeste Pfade" (PDF). Netzwerke, Vol. 23, S. 703-709, 1993. Ссылка . Abgerufen 2008-10-01.
Kurz gesagt, meine Behauptung basiert auf Bertsekas Interpretation von Golden. Ob meine Schlussfolgerung aufsteht oder nicht, Sie können Bertsekas interessant für seine Klassifizierung des Dijkstra-Algorithmus als -Etiketteneinstellung -Methode finden, im Gegensatz zu label correcting -Methoden.
>Es gibt einen Algorithmus, der O (1) hat: Verwandle die Gewichte in Kettenlängen und benutze Schlüsselringe für Knoten (echte Schlüsselringe wie in deiner Tasche). Verbinden Sie die Schlüsselringe mit den richtigen Ketten. Wählen Sie die zwei Knoten und ziehen Sie sie voneinander weg.
Folge den straffen Ketten von einem Knoten zum anderen. Dies ist der kürzeste Weg.
Um dies als Computerprogramm zu implementieren, benötigen Sie zwei Industrieroboter:)
Verwenden Sie für ein realeres Beispiel die Ant-Kolonie-Optimierung , die in kurzer Zeit sehr gute Ergebnisse liefert. Da Sie die Anzahl der Läufe in diesem Algorithmus angeben können, können Sie entscheiden, wie viel Zeit es verbrachte (dh die Laufzeit ist nur von der Anzahl der Knoten abhängig), die Ihnen O (n), aber kein garantiert perfektes Ergebnis liefert.
Tags und Links graph-theory dijkstra