2017-12-14 18 views

Antwort

1

Es ist möglich, ohne alle kürzesten Wege neu zu berechnen, aber immer noch ziemlich teuer O(n^2).

kann also annehmen, dass Sie M mit der Größe n * n, wobei jeder Eintrag M_{i,j} enthält den Abstand von Knoten Knoten ij eine Distanzmatrix. Es wird angenommen, dass M von einem Algorithmus vorberechnet wird.

Wenn nun eine neue Kante e_{i,j} das Graphen zwischen Knoten i und Knoten j mit Kosten w_{i,j} hinzugefügt wird, überprüfen Sie, ob w_{i,j} < M_{i,j}. Wenn nicht, dann muss nichts geändert werden. Aber wenn es gilt, dann könnten sich die kürzesten Pfade im Graphen verbessern.

Dann prüfen Sie für jedes Knotenpaar k, l, ob der Pfad, der durch die neue Kante geht, kürzer ist als der vorher berechnete. Dies kann durch Auswertung des Folgenden geschehen.

M_{k,l} > min (M_{k,i} + w_{i,j} + M_{j,l} , M_{k,j} + w_{j,i} + M_{i,l}) 

Wenn dies hält, dann können Sie M_{k,l} von min (M_{k,i} + w_{i,j} + M_{j,l} , M_{k,j} + w_{j,i} + M_{i,l})

Die oben genannten Arbeiten für unidirektionale Diagramme ersetzen, sondern kann auch auf bidirektionalen Graphen angepasst werden.

Edit 1

Ich glaube fest daran, dass \ Omega (n^2) ist auch das dieses Problem gebunden niedriger. Angenommen, Sie haben zwei getrennte Bereiche des Graphen, die beide n/2 Vertices enthalten. Wenn Sie dann eine neue Kante hinzufügen, die diese Bereiche verbindet, müssen Sie n/2 * n/2 kürzeste Pfade aktualisieren, was zu mindestens O (n^2) Laufzeit führt.

Edit 2

Eine zweite Idee würde versuchen, die obige Gleichung zu nutzen, sondern durch das Graphen zuerst laufen, um alle Paare von Eckpunkten zu finden, die zuerst aktualisiert werden müssen. Die Skizze der Idee ist wie folgt:

Starten Sie eine Dijkstra von Knoten i. Immer wenn Sie einen Knoten k erreichen, prüfen Sie, ob M_{k, i} + w_{i, j} < M_{k, j} falls ja, dann fügen Sie k zu der Menge U von Knoten hinzu, die aktualisiert werden müssen. Wenn nicht, dann können Sie aufhören, weitere Pfade nach k zu erkunden, da kein Knoten "jenseits" k e_ {i, j} für den kürzesten Pfad verwendet.

Dann machen Sie das gleiche für Knoten j. Und führe dann die Aktualisierung von M für alle Knotenpaare in U gemäß den obigen Ideen durch.

+0

Das könnte funktionieren und obwohl es 0 (N^2). Je nach Implementierung kann Dijksra O (ElogV) sein. Ich denke, dass der schlimmste Fall Dijkstra ähnelt, da er alle Paare betreffen könnte. Ich denke jedoch über etwas nach, das die Aktualisierung der Nachbarn nach Bedarf "kräuseln" würde und hoffentlich bei O (1) für die meisten Aktualisierungen anhalten wird. – user2232888

+0

@ user2232888 Die Laufzeit von O (V log V + E) für Dijkstra berechnet nur die Single Source kürzesten Weg. Wie ich Ihre Frage verstanden habe, möchten Sie alle Paare kürzesten Pfad aktualisiert werden. Floyd-Warshall wird dafür O (n^3) nehmen. – SaiBot

+0

Danke, ich denke, dass abhängig von der Größe der Änderung manchmal die Änderung groß sein wird und O wie all_pairs laufen wird. Aber manchmal ist die Änderung klein und betrifft die meisten Paare nicht. dann sollte die Laufzeit O (1) sein Für jetzt habe ich meinen Algorithmus geändert, um diese Art von Berechnung jedes Mal zu vermeiden, wenn der Graph geändert wird. Wenn die Leistung nicht so gut ist, werde ich in ein paar Wochen darauf zurückkommen – user2232888

Verwandte Themen