樹中所有對最短路徑總和

在樹中，「所有節點對最短路徑總和」的術語指的是計算所有節點對的個別最短路徑的總和。一個有效的方法是使用雙重DFS（深度優先搜尋）演算法。在第一次DFS遍歷期間確定所選節點與每個其他節點之間的距離。在第二次DFS遍歷期間再次遍歷樹，將每個節點視為潛在的LCA（最低公共祖先），併計算所選LCA的後代節點對之間的距離總和。使用此方法可以計算出樹中所有節點對最短路徑總和，並確保得到理想的解決方案

使用的方法

• 雙重 DFS（深度優先搜尋）方法

• 動態規劃方法

雙重 DFS（深度優先搜尋）方法

對於樹中所有對最短路徑的總和，我們使用雙重 DFS（深度優先搜尋）方法，該方法涉及兩次 DFS 遍歷。首先，我們計算從任何節點開始到所有其他節點的距離。然後，在第二次 DFS 遍歷期間，我們導航樹，同時將每個節點視為潛在的 LCA。我們在遍歷時計算並求和作為所選 LCA 後代的節點對之間的距離。透過對所有節點重複此過程，我們獲得所有對最短路徑的總和。這個策略對於這個問題非常引人注目，因為它有效地計算了樹中所有節點集之間的距離總和。

演算法

• 樹中的任何節點都可以作為起始節點

• 為了確定從所選的起始節點到所有其他節點的距離，從該節點開始執行深度優先搜尋（DFS）。這些距離應該保存在一個陣列或資料結構中。

• 接下來，在樹上執行第二次深度優先搜尋（DFS），將每個節點視為可能的最近公共祖先（LCA）

• 在第二次 DFS 期間遍歷樹時，計算作為所選 LCA 後代的節點對之間的距離。對於每個 LCA，將這些距離加在一起。

• 對樹中的每個節點重複此過程

• 樹中最有限方式的所有符合的總和由步驟 4 中所有計算距離的總和表示。

Example

的中文翻譯為：

範例

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 10005;
vector<int> graph[MAXN];
int ancestor[MAXN];

int dfs(int node, int lca, int distance) {
   int sum = 0;
   for (int neighbor : graph[node]) {
      if (neighbor != lca) {
         sum += dfs(neighbor, lca, distance + 1);
      }
   }
   return sum + distance;
}

int main() {

   int lca_node = 0;
   int total_sum = 0;

   for (int node = 0; node < MAXN; ++node) {
      if (node != lca_node) {
         total_sum += dfs(node, lca_node, 0);
      }
   }

   cout << "Total sum of distances between descendants of the LCA: " << total_sum << endl;

   return 0;
}

輸出

Total sum of distances between descendants of the LCA: 0

動態規劃方法：

我們首先選擇任一個節點作為根節點，並在動態規劃方法中將樹轉換為有根樹，用於計算樹中所有節點間最短路徑總和。我們利用動態規劃計算每個節點與根節點之間的分割，並將結果儲存在一個陣列中。然後，對於每個節點，我們將其子節點與根節點的分離（已計算）相加，以確定所有其他節點的整體分離。透過這種方式，我們能夠快速計算出所有節點間最短路徑的總數。作為解決此問題的有效方法，此演算法的時間複雜度為O(N)，其中N是樹中節點的數量。

演算法

• 將樹中的任何節點作為根並以樹為根（例如，使用根節點的深度搜尋）以建立有根樹。

• 動態規劃可用來決定每個節點與根的距離。這些距離應該儲存在數組或資料結構中。

• 計算樹中每個節點到所有其他節點的距離的總和：

a.遍歷目前節點的子節點。

b.要考慮通過目前節點的路徑，請將每個子樹的子樹中的節點數以及先前為每個子樹計算的到根的距離相加。

c. 對於活動節點的每個子節點，將這些金額加總

d.將目前節點的總和加入最終結果。

• 樹中所有對最短路徑的總和就是最終結果。

#include <iostream>
#include <vector>

using namespace std;

struct TreeNode {
   int val;
   vector<TreeNode*> children;
};

int dfs(TreeNode* node, vector<int>& distances) {
   int subtree_size = 1;
   for (TreeNode* child : node->children) {
      subtree_size += dfs(child, distances);
      distances[node->val] += distances[child->val] + subtree_size;
   }
   return subtree_size;
}

int sumOfAllPairShortestPaths(TreeNode* root) {
   vector<int> distances(root->val + 1, 0);
   dfs(root, distances);
   int total_sum = 0;
   for (int distance : distances) {
      total_sum += distance;
   }
   return total_sum;
}

int main() {
   TreeNode* root = new TreeNode{0};
   int result = sumOfAllPairShortestPaths(root);
   cout << "Sum of all pair shortest paths in the tree: " << result << endl;
   return 0;
}

輸出

Sum of all pair shortest paths in the tree: 0

結論

樹中所有對最短路徑的總和可以使用 Double DFS（深度優先搜尋）方法或動態規劃來計算。 Double DFS 方法由兩遍組成，首先計算從選定節點到所有其他節點的距離，然後再次遍歷樹，同時將每個節點視為潛在的最低公共祖先(LCA)，以將之間的距離相加後代節點對。動態規劃方法需要遞歸地使用 DFS 來建立樹的根併計算從根到每個其他節點的距離。兩種方法的結果是相同的，並且由樹中所有成對最短路徑的總和組成。兩種演算法之間的決策可能基於特定的實現偏好或樹狀結構，但兩種演算法都提供了有效的解決方案。

以上是樹中所有對最短路徑總和的詳細內容。更多資訊請關注PHP中文網其他相關文章！