複数の頂点から最大距離内でサブグラフを抽出するための効率的なアルゴリズム

Question

簡単な解決策がある場合はアルゴリズム上の問題がありますが、無駄に見えます。私は同じことをするより効率的な方法があるのだろうかと思います。

• 入力：（長さとして解釈）非負辺の重みを持つ大規模なグラフG、頂点vのリスト、および距離dvと同じ長さのリスト

  ここで問題です。

• 出力：サブフラグSがGであり、最大でd[i]の距離にあるすべての頂点で構成され、iの場合はv[i]です。

明白な解決策は、それがd[i]の距離を打つし、各検索は横断部分グラフの和集合を取った後アウトベイルように改変、各v[i]から始まるダイクストラのアルゴリズムを使用することです。しかし、私の使用例では、多くの場合、v[i]の検索ツリーが重複している場合があります。つまり、Dijkstraのアプローチは、私が組合を取る前にオーバーラップの頂点を無駄に複数回横切ることになります。

一つだけ頂点がvに存在した場合には、ダイクストラ法は、頂点の数（私のグラフが疎であるので、私はエッジ項を無視する）ことが|S|を取って、O(|S|log|S|)で実行されます。 vに複数の頂点がある場合、同じ漸近実行時間を達成することは可能ですか？

私の最初のアイデアは、各v[i]からの検索を同じ優先度のキューに組み合わせることでしたが、上記の「ベールアウト」条件はこのアプローチを複雑にします。場合によっては、v[i]から短い距離で頂点に到達することもありますが、もう1つの頂点のサイズがd[j]の場合は、別のv[j]から検索します。

ありがとうございます！

Answer 1

これは、単一のダイクストラ実行の複雑さで解決できます。

dをdの距離の最大値とします。

新しい開始頂点を定義し、それはVの頂点のそれぞれに縁与える。

開始とVとの間のエッジの長さ[i]をD-Dに設定されるべきである[I]。

この新しいグラフでは、Sは開始頂点の長さD内のすべての頂点によって与えられるため、開始頂点にDijkstraを適用します。