APSP 問題のよく知られたアルゴリズム (Dijkstra/Floyd-Warshall など) のいずれかをウォーム スタートして、時間の複雑さを軽減し、場合によっては計算時間を短縮することは可能ですか?
グラフが NxN 行列で表されているとしましょう。私は、1 つまたは複数の行列エントリ (<< N)、つまり、対応する頂点間の距離、アルゴリズム プロシージャへの 2 つの呼び出し間の変更のみを考慮しています。アルゴリズムの 2 回目の呼び出しで計算を高速化するために、最初の呼び出しの解と行列の増分変更のみを使用できますか? 私は主に密行列を見ていますが、疎行列の既知の方法があれば、遠慮なく共有してください。ありがとう。
APSP のインクリメンタル アルゴリズムについては知りません。ただし、Lifelong Planning A* (別名「LPA*」、「Incremental A*」とも呼ばれることはめったにありません) と呼ばれる SSSP を解決するための A* の増分バージョンがあり、これは 2 番目の段落で質問しているようです。
元の論文へのリンクはこちらです。詳細については、A* バリエーションに関するこの投稿を参照してください。
興味深い研究論文は次のとおりです:動的全ペア最短経路アルゴリズムの実験的分析 [Demetrescu, Emiliozzi, Italiano ]
すべてのペアの最短経路問題に対する動的アルゴリズムに関する広範な計算研究の結果を提示します。King [18] および Demetrescu と Italiano [7] の最近の動的アルゴリズムの実装について説明し、それらを Ramalingam と Reps [25] の動的アルゴリズム、およびランダム、実世界、ハード インスタンスの静的アルゴリズムと比較します。 . 私たちの実験データは、いくつかの動的アルゴリズムとそのアルゴリズム技術が多くの状況で実際に役立つことを示唆しています。
別の興味深い分散アルゴリズムは、動的ネットワーク上の分散最短パスのための新しいアルゴリズムの設計です [Cicerone、D'Angelo、Di Stefano、Frigioni、Maurizio] :
エッジ更新操作がネットワークに発生している間に、分散ネットワーク内のすべてのペアの最短パスを動的に更新する問題を研究します。1 つまたは複数の他のエッジ更新が処理中である間にエッジ更新が発生する動的ネットワークの実際のケースを検討します。
All Pairs Shortest Paths on Dynamic Networksを検索すると、より多くのリソースを見つけることができます。