最短経路を動的に更新する

Question

私はすべての最短経路（またはその長さ）を頻繁に知る必要があるグラフを持っています。私はそれらを再計算したくないので、それらを単純な配列に格納してそこから取得するだけです。しかし、グラフは時間の経過とともに変化する可能性があるので、与えられた時間にグラフを再計算する必要があります。

は、今のところ、以下の変更が発生する可能性があります：

• 新しいエッジを追加するエッジ

• の長さを変更するグラフ

• に、ノードとエッジを追加しますグラフの

• エッジの削除またはノードの削除

すべての場合、すべてのノードは常に接続され、すべてのエッジは正の重みを持ちます。また、グラフは無向である。操作のシーケンスは、すべてのノードが常にグラフの同じコンポーネントから来るようなものです。この前にノードまたはエッジが削除された場合、グラフが決して分離されないように、他のノードおよびエッジが追加されます。

今のところ私は更新を行い、すべての変更をグラフ構造を通して伝播する予定です。しかし、私はこれを正しく処理する方法はまだわかりません。どのようにキャッシュされた長さのこれらの更新を達成しようとしますか？

EDIT：あなたのいくつかが指摘したようにノードが追加されたり、リンクが変更されたとき

すべてを再計算するneccessaryかもしれません。これは、たとえば、すべての距離が更新によって変化する場合などです。しかし、グラフを使って変更を伝播し、dijkstrasのやり方と同様の緩和を行うと、最適な順序を選択しない可能性があるため、同じノードを複数回リラックスさせる必要があります。問題は、リラクゼーションの手順をどのようにするかということです。そのため、できるだけ複数の更新を避けるようにしています。

これは実際の考えがなければ意味をなさないものですが、これでもう少し明確になることを願っています。

Answer 1

D* family of search algorithmsは、動的に変化するグラフの短絡経路の更新に関係しています。このアルゴリズムは、移動ロボットの経路計画問題のために開発されました。アルゴリズムはゴールから現在のロボットの位置までの最短経路のみを返しますが、すべての最短経路問題についても簿記および更新ルールを使用することができます。

Answer 2

エッジ/ノードを簡単に削除するケースを処理できます。ノード間の実際のパスを追跡するだけです。エッジ/ノードが削除されたら、パスを通って変更の影響を受けるパスを確認します。これらの最短経路を再計算します。

エッジウェイトを増やしている場合は、同じテクニックを使用できます。

他のケースは扱いがかなり困難です。私は再計算を高速化するどんなアルゴリズム/データ構造も知らない。