graph - グラフで、ノードのグループに最も近いノードを見つける方法は?

Question

平面である必要のない、無向で重みのないグラフがあります。グラフのノードのサブセット (真のサブセット) もあり、サブセット内のすべてのノードまでの距離の最小合計で、サブセットに属さないノードを見つける必要があります。

これまでのところ、サブセット内の各ノードから開始する息優先検索を実装しました。最初に発生する交差点が探しているノードです。残念ながら、グラフには多数のノードが含まれているため、実行が遅すぎます。

Answer 1

全ペア最短経路アルゴリズムを使用すると、O(V^3) 時間ですべてのノード間の距離を見つけることができます。Floyd-warshallを参照してください。その後の合計は少なくとも2次になり、最悪の場合も3次になると思います。これは非常に簡単で、それほど速くはありませんが、現在行っている方法よりも桁違いに速いように思えます。