Ist es möglich, einen der bekannten Algorithmen (Dijkstra/Floyd-Warshall usw.) für das APSP-Problem zu erwärmen, um die Zeitkomplexität und möglicherweise die Rechenzeit zu reduzieren?Alle Paare kürzester Weg - Warmstart?
Nehmen wir an, der Graph wird durch eine NxN-Matrix dargestellt. Ich betrachte nur Änderungen in einem oder mehreren Matrixeinträgen (<N1212), d. H. Abstand zwischen den entsprechenden Scheitelpunkten, zwischen irgendwelchen 2 Aufrufen der Algorithmusprozedur. Können wir die Lösung aus dem ersten Aufruf und nur die inkrementellen Änderungen der Matrix verwenden, um die Berechnung beim zweiten Aufruf des Algorithmus zu beschleunigen? Ich schaue hauptsächlich auf dichte Matrizen, aber wenn es Methoden für spärliche Matrizen gibt, können Sie diese gerne teilen. Vielen Dank.
Ich bin eher an Antworten auf diese Frage interessiert, aber ich denke, es ist besser, es auf http://cs.stackexchange.com/ zu veröffentlichen. Vielleicht möchten Sie weitere Details wie, ob Sie die gleiche Quelle suchen und über verschiedene Anrufe sinken (in diesem Fall denke ich, dass es möglich sein könnte, einige Werte wiederverwenden) – yanhan
Danke für den Tipp - ich werde es bei der cs staplexchange auch. Ich interessiere mich mehr für den allgemeinen Fall der Bestimmung der Abstände zwischen allen Paaren von Knoten/Scheitelpunkten bei jedem Aufruf (und wenn möglich auch dem Pfad mit den geringsten Kosten). – user3282279
FYI: Ich bemerkte die folgende Diskussion auf cs staplexchange zu diesem Thema von dynamischen Diagrammen: http://cs.stackexchange.com/q/7250/14479 – user3282279