Abrufen des kürzesten Pfads eines dynamischen Diagramms

Ich studiere derzeit die kürzesten Wege in gerichteten Graphen. Es gibt viele effiziente Algorithmen, um den kürzesten Weg in einem Netzwerk zu finden, wie zum Beispiel die von dijkstra oder bellman-ford. Was aber, wenn der Graph dynamisch ist? Mit "dynamisch" meine ich, dass wir während der Ausführung des Programms Scheitelpunkte einfügen oder entfernen können. Ich versuche, einen effizienten Algorithmus zum Aktualisieren der kürzesten Pfade von einem Scheitelpunkt zu jedem anderen Scheitelpunkt nach dem Einfügen einer Kante , ohne den Algorithmus für kürzeste Pfade erneut im neuen Diagramm ausführen zu müssen. Wie kann ich das machen? Danke im Voraus.$v$$u$$e$

• Hinweis: Die Änderungen können nach der ersten Iteration des Algorithmus vorgenommen werden
• Anmerkung [2]: Es werden zwei Knoten angegeben, die Quelle und das Ziel. Ich muss den kürzesten Weg zwischen diesen Knoten finden. Wenn der Graph aktualisiert wird, muss ich nur aktualisieren , was der kürzeste Weg zwischen und .t π ( s , t ) s $s$$t$$\pi(s,t)$$s$$t$
• Anmerkung [3]: Ich interessiere mich nur für den Randeinfügungsfall.

Eine formale Definition : Gegeben sei ein Graph . Definieren eine Aktualisierungsoperation als 1) , um ein Einsetzen einer Kante zu bzw. 2) aa Löschen einer Kante von . Ziel ist es, die Kosten aller Paare auf kürzestem Weg nach einer Aktualisierungsoperation effizient zu ermitteln. Mit effizient ist gemeint, dass mindestens ein All-Pairs-Shortest-Path-Algorithmus, wie z. B. der Bellman-Ford-Algorithmus, nach jeder Aktualisierungsoperation besser ausgeführt werden sollte.e E e $G = (V,E)$$e$$E$$e$$E$

Bearbeiten: Unten gibt es eine vereinfachte Version des Problems:

Es ist ein gewichteter Graph gegeben, der aus unidirektionalen Kanten und zwei kritischen Eckpunkten und . Ein Satz von bidirektionalen Kandidatenkanten ist ebenfalls gegeben. Ich muss eine Kante um den Abstand von zu zu minimieren .s t C ( u , v ) ∈ C s $G(V,E)$$s$$t$$C$$(u,v) \in C$$s$$t$

Das Problem ist, wie Sie wahrscheinlich bemerkt haben, ein ziemlich schwieriges Problem. Das Überprüfen des Webs führt zu einigen komplexen Instanzen, die Sie wahrscheinlich nicht benötigen werden. Hier ist eine Lösung - wie erforderlich (dh Sie müssen nicht alles von Grund auf neu berechnen).

Wenn Sie eine Kante hinzufügen und dann Ihre bereits erstellte Distanzmatrix verwenden, gehen Sie wie folgt vor:$(u,v)$

Überprüfen Sie für jedes Knotenpaar und y , ob d ( ( x , u ) ) + c ( ( u , v ) ) + d ( ( v , y ) ) < d ( ( x , y ) ) - dies ist möglich in O ( n 2 ), da Sie jedes Knotenpaar vergleichen.$x$$y$$d((x,u)) + c((u,v)) + d((v,y)) < d((x,y))$$O(n^2)$

Für den Fall der Kantenlöschung: Wenn die Distanzmatrix bereits erstellt ist, können Sie für jeden Knoten einen Baum mit dem kürzesten Pfad haben, der bei u verwurzelt ist . Befindet sich die gelöschte Kante e nicht in diesem Baum, sind die kürzesten Wege von u zu jedem anderen nicht betroffen - (sie bleiben gleich).$u$$u$$e$$u$

$e$$u$$v$$\pi(u,v)$$e$$u$$v$

Wenn Sie bessere Ergebnisse erzielen möchten, schauen Sie sich Folgendes an:

1. Demetrescu, Camil und Giuseppe F. Italiano. "Ein neuer Ansatz zur Dynamik aller Paare auf kürzestem Weg." Journal of the ACM (JACM) 51.6 (2004): 968-992. (kann frei von Google gefunden werden)

2. oder schauen Sie sich diese schön geschriebene Umfrage an

Das Problem, nach dem Sie fragen, sind bekannte algorithmische Probleme. Es ist eigentlich noch offen, wie schwer dieses Problem genau ist. Sie sollten auch wissen, dass es verschiedene Inkarnationen dieses Problems gibt. Im Gegensatz zu dem, wonach Sie fragen, werden normalerweise nur die Entfernungen zurückgegeben, wohingegen Sie nach den tatsächlich kürzesten Wegen fragen. Beachten Sie, dass diese Pfade bereits sehr lang sein können. Dynamische Graph-Algorithmen unterscheiden nur zwischen Randlöschungen (dekrementelle dg-Algorithmen), Randeinfügungen (inkrementelle dg-Algorithmen) und Randeinfügungen und -löschungen (voll dynamische dg-Algorithmen). Sie interessieren sich daher für inkrementelle Algorithmen.

$O(n^2(\log n +\log^2 (1+m/n))$$O(1)$$O(n\log n)$Kanten, dann könnte man mit Dijkstra und Fibonacci-Heaps einfach von Grund auf neu berechnen und die gleiche Laufzeit wie in Thorups Algorithmus erhalten. Wenn Ihre Grafiken nicht zu dicht sind, würde ich die Verwendung von Dijkstra empfehlen.

Mir ist kein besserer inkrementeller Algorithmus bekannt. Sie sollten jedoch eine Websuche durchführen, wenn für dieses spezielle Problem neuere Ergebnisse vorliegen.

Ich glaube, der AD * -Algorithmus könnte Ihnen helfen.

http://www.cs.cmu.edu/~ggordon/likhachev-etal.anytime-dstar.pdf

Wenn aktualisierte Informationen bezüglich des zugrunde liegenden Graphen empfangen werden, repariert der Algorithmus schrittweise seine vorherige Lösung. Das Ergebnis ist ein Ansatz, der die Vorteile von jederzeit verfügbaren und inkrementellen Planern kombiniert, um effiziente Lösungen für komplexe, dynamische Suchprobleme bereitzustellen

AD * -Highlights: Es ist "jederzeit", was bedeutet, dass Sie sehr schnell eine "suboptimale Lösung" erhalten, auch wenn dies möglicherweise nicht die beste ist. Wenn genügend Zeit zur Verfügung steht, wird die optimale Lösung gefunden. Außerdem können Sie die suboptimale Lösung durch eine benutzerdefinierte Konstante so einschränken, dass sie nicht schlechter als die optimale Lösung ist. Dies gibt Ihnen die Möglichkeit, dies in einem Echtzeit-Planungsszenario zu verwenden, in dem eine in Ordnung befindliche Lösung (in der 'in Ordnung' theoretisch begrenzt ist) besser ist als überhaupt keine Lösung.

http://www.cs.cmu.edu/~maxim/software.html