树中所有对最短路径之和

在树中，“所有节点对最短路径之和”的术语指的是计算所有节点对的个别最短路径的总和。一种有效的方法是使用双重DFS（深度优先搜索）算法。在第一次DFS遍历期间确定所选节点与每个其他节点之间的距离。在第二次DFS遍历期间再次遍历树，将每个节点视为潜在的LCA（最低公共祖先），并计算所选LCA的后代节点对之间的距离之和。使用这种方法可以计算出树中所有节点对最短路径之和，并确保得到一个理想的解决方案

使用的方法

• Double DFS (Depth-First Search) Approach

• Dynamic Programming Approach

Double DFS (Depth-First Search) Approach

For the total of all pair shortest paths in a tree, we use the Double DFS (Depth-First Search) approach, which involves two DFS passes. To begin, we compute the distances to all other nodes starting from any node. Then, during the second DFS pass, we navigate the tree while considering each node as a potential LCA. We compute and sum the distances between pairs of nodes that are offspring of the selected LCA while traversing. We obtain the total sum of all pair shortest paths by repeating this process for all nodes. This strategy is exceptionally compelling for this issue since it productively calculates the sum of distances between all sets of nodes in a tree.

算法

• 树中的任何节点都可以作为起始节点

• 为了确定从选择的起始节点到所有其他节点的距离，从该节点开始执行深度优先搜索（DFS）。这些距离应该保存在一个数组或数据结构中。

• 接下来，在树上运行第二次深度优先搜索（DFS），将每个节点视为可能的最近公共祖先（LCA）

• Calculate the distances between pairs of nodes that are descendants of the chosen LCA while traversing the tree during the second DFS. For each LCA, add these distances together.

• 对树中的每个节点重复此过程

• The whole sum of all matches in the most limited ways within the tree is represented by the sum of all calculated distances from step 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;
}

Output

Total sum of distances between descendants of the LCA: 0

动态规划方法：

我们首先选择任意一个节点作为根节点，并在动态规划方法中将树转化为有根树，用于计算树中所有节点间最短路径之和。我们利用动态规划计算每个节点与根节点之间的分割，并将结果存储在一个数组中。然后，对于每个节点，我们将其子节点与根节点的分离（已计算）相加，以确定所有其他节点的整体分离。通过这种方式，我们能够快速计算出所有节点间最短路径的总数。作为解决该问题的有效方法，该算法的时间复杂度为O(N)，其中N是树中节点的数量。

算法

• Make any node in the tree the root and root the tree (for example, using a deep search of the root node) to create a rooted tree.

• Dynamic programming can be used to determine how far each node is from the root. Those distances should be stored in an array or data structure.

• 计算树中每个节点到所有其他节点的距离的总和：

a. Move through the current node's children.

b. To account for paths that pass through the current node, add the number of nodes in each child's subtree and the distance to the root that was previously calculated for each child.

c. 对于活动节点的每个子节点，将这些金额相加

d. To the final result, add the total for the current node.

• The total sum of all pair shortest paths in the tree is the final result.

#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;
}

Output

Sum of all pair shortest paths in the tree: 0

结论

The sum of all pair shortest paths in a tree can be calculated using the Double DFS (Depth-First Search) approach or dynamic programming. The Double DFS approach consists of two passes, where we first compute the distances from a selected node to all other nodes, and then we traverse the tree again while considering each node as a potential Lowest Common Ancestor (LCA), to add up distances between pairs of descendant nodes. The Dynamic Programming approach entails recursively using DFS to root the tree and calculate distances from the root to every other node. The results of both approaches are identical and consist of the sum of all pairwise shortest paths in the tree.The decision between the two algorithms may be based on particular implementation preferences or tree structures, but both algorithms offer effective solutions.