Angenommen, wir erhalten einen gewichteten Graphen G (V, E).
Das Diagramm enthält N Scheitelpunkte ( Von 0 bis N-1 nummeriert ) und M bidirektionale Kanten .
Jede Kante (vi, vj) hat positiven Abstand d (dh der Abstand zwischen den beiden Eckpunkten vivj ist d)
Es gibt fast eine Kante zwischen zwei Ecken und auch keine Selbstschleife (dh keine Kante verbindet einen Scheitelpunkt mit selbst.)
Auch erhalten wir S den Quellknoten und D den Zielknoten.
Lassen Sie Q die Anzahl der Abfragen sein, jede Abfrage enthält eine Kante e (x, y) .
Für jede Abfrage müssen wir den kürzesten Pfad von der Quelle S zum Ziel D finden, vorausgesetzt, dass die Kante (x, y) im ursprünglichen Diagramm nicht vorhanden ist. Wenn kein Pfad von S nach D existiert, müssen wir Nr.
druckenEinschränkungen sind hoch 0 & lt; = (N, Q, M) & lt; = 25000
Wie löst man dieses Problem effizient?
Bis jetzt habe ich den einfachen Dijakstra-Algorithmus implementiert.
Für jede Abfrage Q jedes Mal, wenn ich (x, y) dem Infinity zuordne und Dijakstra kürzesten Pfad finden .
Aber dieser Ansatz wird sehr langsam sein, da die Gesamtkomplexität Q ist (Zeitkomplexität des Dijastra Shortes-Pfads) *
Beispiel ::
%Vor%Berechnen Sie zuerst den kürzesten Pfadbaum vom Quellknoten zum Ziel.
Zweitens, führen Sie eine Schleife über alle Abfragen durch und schneiden Sie den kürzesten Pfad an der von der Abfrage angegebenen Kante ab; dies definiert ein Min-Cut-Problem, bei dem Sie den Abstand zwischen dem Quellknoten und der Grenze einer Partition und der Grenze der anderen und des Ziels haben; Sie können dieses Problem sehr einfach berechnen, höchstens O(|E|) .
Somit benötigt dieser Algorithmus O(Q|E| + |V|log|V|) , asymptotisch schneller als die naive Lösung, wenn |V|log|V| > |E| .
Diese Lösung verwendet die Berechnung von Dijkstra wieder, verarbeitet jedoch jede Abfrage einzeln. Vielleicht gibt es also Raum für Verbesserungen, indem Sie die in einer vorherigen Abfrage in aufeinanderfolgenden Abfragen ausgeführte Arbeit nutzen, indem Sie die Form des durch die Kante induzierten Schnitts beobachten.
>Bei jeder Abfrage ändert sich das Diagramm nur geringfügig, so dass Sie einen Großteil Ihrer Berechnungen wiederverwenden können.
Ich schlage folgenden Ansatz vor:
Wenn Sie das Dijkstra in Schritt 2 ausführen, können Sie den abgeschnittenen Teil des Baums T wie folgt wiederverwenden: Jedes Mal, wenn Sie einen Knoten dauerhaft markieren wollen (der Knoten ist nicht der Knoten) In T ') können Sie den gesamten Teilbaum dieses Knotens (vom ursprünglichen Baum T ) an Ihren neuen Baum für den kürzesten Pfad anhängen und alle Knoten als permanent kennzeichnen.
Auf diese Weise können Sie so viele Informationen wie möglich aus dem ersten Lauf des kürzesten Pfads wiederverwenden.
In Ihrem Beispiel würde dies bedeuten:
Berechnen Sie den kürzesten Pfadbaum: 0- & gt; 1- & gt; 2- & gt; 3- & gt; 4- & gt; 5 (In diesem Fall eine sehr einfache)
Nehmen wir nun an, wir erhalten Abfrage (1,2).
Wir beschneiden die Kante (1,2) und lassen uns zurück 0- & gt; 1
Von dort beginnen wir Dijkstra, 2 und 3 als nächste permanent markierte Knoten zu bekommen. Wir verbinden 1 zu 2 und 1 zu 3 in dem neuen kürzesten Pfadbaum und fügen den alten Teilbaum von 3 hinzu: 2 & lt; -0- & gt; 1- & gt; 3- & gt; 4- & gt; 5
Wir haben also den kürzesten Weg mit nur einem zusätzlichen Schritt des Dijkstras-Algorithmus.
Die Korrektheit des Algorithmus folgt aus allen Pfaden in der Struktur T , die höchstens so lang sind wie im neuen Graphen aus der Abfrage (wobei jeder kürzeste Pfad nur länger sein kann). Daher können wir jeden Pfad aus dem Baum, der noch machbar ist (d. H. Wo keine Kante entfernt wurde), wiederverwenden.
Wenn Leistung sehr wichtig ist, können Sie die Dijkstra-Performance durch viele Implementierungstricks verbessern. Ein guter Einstiegspunkt hierfür könnte die DIMACS-Lösung für den kürzesten Pfad zur Implementierung sein .
Eine einfache Optimierung: Führen Sie Dijkstra zuerst auf einem vollständigen Graphen (ohne Kanten entfernt).
Überprüfen Sie dann für jede Abfrage, ob die angeforderte Kante zu dem kürzesten Pfad gehört. Wenn nicht - das Entfernen dieser Kante wird keinen Unterschied machen.
Tags und Links algorithm shortest-path