グラフの更新中に最短経路を維持する

Question

すべてのペア間の距離を知りたい（例えばdijkstra、具体的にはnetworkxを使用しています） エッジがグラフに追加されると、ゼロから再計算せずに距離を更新します。

どうすればいいですか？ ありがとう

Answer 1

すべての最短経路を再計算する必要はありませんが、まだかなり高価ですO(n^2)。

だからあなたは大きさnの*との距離行列Mを持っていると仮定することができますnは各エントリM_{i,j}はjをノード間iからの距離が含まれています。 Mはあるアルゴリズムによってあらかじめ計算されていると仮定される。今

新しいエッジe_{i,j}はw_{i,j} < M_{i,j}かどうかをチェック、コストw_{i,j}でノードiとノードj間のグラフに追加されている場合。そうでない場合、変更する必要はありません。しかし、それが成立すれば、グラフの最短経路が改善されるかもしれない。

次に、新しいエッジを経由するパスが以前に計算されたものよりも短いかどうかをチェックk, l各ノード対のため。これは、以下を評価することによって行うことができます。

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

これが保持しているなら、あなたは一方向のグラフのM_{k,l}

min (M_{k,i} + w_{i,j} + M_{j,l} , M_{k,j} + w_{j,i} + M_{i,l})ことによって、上記作品を置き換えることができますが、同様に双方向のグラフに適合させることができます。

編集1

私はしっかりと\オメガ（N^2）も、この問題の下界であると信じています。 n/2頂点を含むグラフの2つの切断された領域があるとします。次に、これらの領域を接続する新しいエッジを追加すると、少なくともO（n^2）ランタイムになるn/2 * n/2の最短パスを更新する必要があります。

編集2

二アイデアは、上記の式を利用するが、まず最初に更新する必要が頂点のすべてのペアを見つけるために、グラフを介して実行しようとするだろう。次のようなアイデアのスケッチは次のとおりです。

私はノードからダイクストラを起動し

。あなたが頂点kを達するたびはい、更新する必要が頂点の集合UにKを追加する場合は、M_{k, i} + w_{i, j} < M_{k, j}かどうかを確認します。ない場合は、K「を超えて」は頂点が最短経路のためにE_ {I、J}を使用しないので、k個以下のさらなる経路を探索停止することができます。

そして、ノードjのために同じことを行います。そして、上記の考え方に従って、Uのすべての頂点対に対してMの更新を実行します。