在圖中，如何找到一組節點的最近節點？

Question

我有一個無向圖，它不必是平面的。我也有一個圖的節點子集（真子集），我需要找到一個不屬於子集的節點，並且與子集中所有節點的距離最小。

到目前爲止，我已經從子集中的每個節點開始執行呼吸優先搜索，而首先發生的交集就是我正在尋找的節點。不幸的是，由於圖形包含大量節點，所以運行速度太慢。

Answer 1

全對最短路徑算法允許您在O（V^3）時間內找到所有節點之間的距離，請參見Floyd-warshall。然後求和後至少是二次的，我認爲最壞的情況也是立方的。這是一種非常簡單而不是非常快速的方式，但它聽起來可能比你現在正在做的要快一個數量級。