重み付きグラフGとその最短経路距離の行列デルタが与えられます。したがって、delta（i、j）は、iからjへの最短経路の重みを示します（iとjはグラフの2つの頂点です）。デルタは最初に最短経路の値を含めて与えられます。エッジEの重みが突然WからW'に減少します。O（n ^ 2）のdelta（i、j）を更新する方法は？（n =グラフの頂点の数）問題は、O（n ^ 3）の複雑さが最も高い全ペア最短経路を再度計算しないことです。問題はデルタの更新であるため、すべてのペアの最短パスを再計算する必要はありません。
より明確に：私たちが持っているのはグラフとそのデルタ行列だけです。デルタ行列には、最短経路の値だけが含まれます。次に、グラフの変更に応じてデルタ行列を更新します。エッジの重みが減少します。O（n ^ 2）で更新する方法は？
ノード a からノード b へのエッジ E の重みが減少した場合、ノード i からノード j への最短経路長を一定時間で更新できます。i から j への新しい最短パスは、古いものと同じか、a から b へのエッジを含んでいます。a から b へのエッジが含まれる場合、その長さはdelta(i, a) + edge(a,b) + delta(b, j)です。
このことから、行列全体を更新する O(n^2) アルゴリズムは、無向グラフを扱うアルゴリズムと同様に自明です。
ダイクストラのアルゴリズムを読んでください。これが、これらの最短経路問題を実行する方法であり、とにかくO（n ^ 2）未満で実行されます。
編集ここにはいくつかの微妙な点があります。グラフ内の任意のiから任意のjへの最短経路が提供されているようで、行列全体を更新する必要があるようです。この行列の反復はn^2です。これは、行列が1つおきにすべてのノード、またはn*nまたはn^2であるためです。n ^ 2はダイクストラのO（| E | + | V | log | V |）パフォーマンスよりも大きいため、デルタ行列のすべてのエントリに対してダイクストラのアルゴリズムを再実行するだけでは、このパフォーマンスクラスは変更されません。私はこれを正しく読んでいますか、それともbig-Oを覚えていませんか？
編集編集私はbig-Oを覚えていないようです。行列を反復処理するとn^2になり、それぞれのダイクストラ法は追加のオーバーヘッドになります。どのパスW'が含まれているのかを正確に把握しないと、一般的なケースでこれを行う方法がわかりません...これは、各ペアをチェックする必要があることを意味しているようです。したがって、各ペアを一定時間で更新するか、配列の重要な部分をチェックしないようにする必要があります。