Kürzester Weg in Abwesenheit der gegebenen Kante

Question

Angenommen, wir erhalten einen gewichteten Graphen G (V, E).

Der Graph enthält N Vertices (numeriert von 0 bis N-1) und M Bidirectional Kanten.

Jede Kante (vi, vj)postive Abstand d (dh der Abstand zwischen den beiden Scheitel vivj ist d)

Es ist atmost eine Kante zwischen zwei beliebigen Eckpunkt und zudem gibt es hat keine Selbstschleife (ie.no Kante verbindet einen Scheitelpunkt selbst.)

auch sind wir S die Quelle liegenden Vertex und D der Zielknoten.

lassen Q die Anzahl von Abfragen, die jeweils eine Kante Abfrage enthält e (x, y).

Für jede Abfrage müssen wir den kürzesten Pfad von der Quelle S zu Ziel D finden, vorausgesetzt, dass die Kante (x, y) im ursprünglichen Diagramm nicht vorhanden ist. Wenn kein jeder Pfad von S bis D vorhanden ist, dann müssen wir Nr

Constraints sind hoch 0 < = (N, Q, M) < drucken = 25000

Wie dieses Problem zu lösen Problem effizient?

Bis jetzt, was ich tat umgesetzt wird, um den einfachen Dijakstra Algorithmus.

Für jede Q-Abfrage, bin ich jedes Mal Zuordnung (x, y) zur Unendlichkeit und Dijakstra kürzesten Weg zu finden.

Aber dieser Ansatz wird sehr langsam sein als die Gesamtkomplexität Q (Zeitkomplexität von Dijastra Shortes Pfad) wird *

Beispiel ::

N=6,M=9 
S=0 ,D=5 

(u,v,cost(u,v)) 
0 2 4 
3 5 8 
3 4 1 
2 3 1 
0 1 1 
4 5 1 
2 4 5 
1 2 1 
1 3 3 

Total Queries =6 

Query edge=(0,1) Answer=7 
Query edge=(0,2) Answer=5 
Query edge=(1,3) Answer=5 
Query edge=(2,3) Answer=6 
Query edge=(4,5) Answer=11 
Query edge=(3,4) Answer=8 

Answer 1

Zuerst berechnet den kürzesten Pfadbaum von dem Quellenknoten zum Ziel.

Zweitens Schleife über alle Abfragen und schneiden Sie den kürzesten Pfad an der Kante durch die Abfrage angegeben; 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|).

Daher erfordert 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 Dijkstra-Berechnung erneut, verarbeitet jedoch jede Abfrage einzeln. Es gibt also möglicherweise Raum für Verbesserungen, indem die in einer vorherigen Abfrage in aufeinanderfolgenden Abfragen ausgeführte Arbeit verwendet wird, indem die Form des Schnitts durch die Kante beobachtet wird.

Answer 2

Eine einfache Optimierung: erster Dijkstra läuft auf vollständiger Graph (ohne Kanten entfernt).

Dann wird für jede Abfrage - überprüfen, ob die angeforderte Kante zu diesem kürzesten Weg gehört. Wenn nicht - das Entfernen dieser Kante macht keinen Unterschied.

Answer 3

Bei jeder Abfrage ändert sich das Diagramm nur geringfügig, so dass Sie viele Ihrer Berechnungen wiederverwenden können.

Ich schlage vor, den folgenden Ansatz:

1. Berechnen Sie den kürzesten Weg von S an alle anderen Knoten (Dijkstras Algorithmus tut das für Sie bereits). Dadurch erhalten Sie den kürzesten Pfadbaum T.
2. Nehmen Sie für jede Abfrage diesen Baum, abgeschnitten von der Kante (x, y) aus der Abfrage. Dies könnte der ursprüngliche Baum sein (wenn (x, y) kein wo auf dem Baum war) oder ein kleinerer Baum T '.
   • Wenn D in der T ‚, können Sie den ursprünglichen kürzesten Weg nehmen kann
   • Ansonsten Dijkstra starten, aber verwenden Sie die Etiketten, die Sie bereits aus der T haben‘ (diese Wege sind bereits kleinste) als dauerhafte Etiketten.

Wenn Sie den Dijkstra in Schritt 2 ausführen können Sie die beschnittenen Teil des Baumes T auf folgende Weise wieder verwenden: Jedes Mal, wenn Sie einen Knoten permanent markieren möchten (was einer der Knoten ist nicht in T ') können Sie den gesamten Teilbaum dieses Knotens (vom ursprünglichen Baum T) an Ihren neuen Baum des kürzesten Pfads anhängen und alle Knoten dauerhaft benennen.

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:

Compute kürzester Weg Baum: 0-> 1-> 2-> 3-> 4-> 5 (in diesem Fall ein sehr einfachen)

Nehmen wir jetzt an, wir bekommen Abfrage (1,2).

Wir stutzen Rand (1,2) verlässt uns mit 0-> 1

Von dort aus starten wir Dijkstra immer 2 und 3 als nächste permanent markierten Knoten. Wir verbinden 1 bis 2 und 1 bis 3 in dem neuen kürzesten Weg Baum und befestigen Sie den alten Teilbaum von 3: -0-> 1-> 3-> 4-> 5

Also haben wir die kürzeste Pfad mit nur einem zusätzlichen Schritt des Dijkstras-Algorithmus.

---

Die Richtigkeit des Algorithmus ergibt sich aus allen Pfaden in tree T höchstens so lange, wie in der neuen Graphen aus der Abfrage ist (wo nur jeder kürzesten Weg 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 die Leistung sehr wichtig ist, können Sie die Leistung von Dijkstra durch viele Implementierungstricks verbessern. Ein guter Einstiegspunkt hierfür könnte der DIMACS Shortest Path Implementation Challenge sein.