The sum of all pairs of shortest paths in the tree

In trees, the term "sum of the shortest paths of all pairs of nodes" refers to the calculation of the sum of the individual shortest paths of all pairs of nodes. An effective method is to use the dual DFS (depth first search) algorithm. The distance between the selected node and every other node is determined during the first DFS pass. The tree is traversed again during the second DFS pass, considering each node as a potential LCA (lowest common ancestor) and calculating the sum of distances between pairs of descendant nodes of the selected LCA. Using this method you can calculate the sum of the shortest paths for all pairs of nodes in the tree and ensure an ideal solution

usage instructions

• Double DFS (depth first search) method

• Dynamic programming method

Double DFS (depth first search) method

For the sum of all pairs of shortest paths in the tree, we use a dual DFS (depth-first search) method, which involves two DFS passes. First, we calculate the distance from any node to all other nodes. Then, during the second DFS traversal, we navigate the tree while considering each node as a potential LCA. We calculate and sum the distances between pairs of nodes that are descendants of the selected LCA while traversing. By repeating this process for all nodes, we obtain the sum of all pairs of shortest paths. This strategy is very compelling for this problem because it effectively computes the sum of distances between all sets of nodes in the tree.

algorithm

• Any node in the tree can be used as the starting node

• To determine the distance from the selected starting node to all other nodes, perform a depth-first search (DFS) starting from that node. These distances should be saved in an array or data structure.

• Next, run a second depth-first search (DFS) on the tree, considering each node as its possible nearest common ancestor (LCA)

• During the second DFS traversal of the tree, calculate the distance between pairs of nodes that are descendants of the selected LCA. For each LCA, these distances are added together.

• Repeat this process for each node in the tree

• The sum of all matches in the most limited way in the tree is represented by the sum of all calculated distances in step 4.

The Chinese translation of

Example

is:

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

Dynamic programming method:

We first select any node as the root node, and convert the tree into a rooted tree in the dynamic programming method, which is used to calculate the sum of the shortest paths between all nodes in the tree. We use dynamic programming to calculate the split between each node and the root node and store the results in an array. Then, for each node, we add the (computed) separations of its children from the root node to determine the overall separation of all other nodes. In this way, we can quickly calculate the total number of shortest paths between all nodes. As an efficient way to solve this problem, the time complexity of this algorithm is O(N), where N is the number of nodes in the tree.

algorithm

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

• Dynamic programming can be used to determine the distance of each node from the root. These distances should be stored in an array or data structure.

• Calculate the sum of the distances from each node to all other nodes in the tree:

a. Traverse the child nodes of the current node.

b. To consider the path through the current node, add the number of nodes in the subtree for each subtree and the distance to the root previously calculated for each subtree.

c. For each child node of the active node, add these amounts

d. Add the current node's total to the final result.

• The sum of all pairs of 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

in conclusion

The sum of all pairs of shortest paths in the tree can be calculated using the Double DFS (Depth First Search) method or dynamic programming. The Double DFS method consists of two passes, first calculating the distance from the selected node to all other nodes, and then traversing the tree again while treating each node as a potential lowest common ancestor (LCA) to sum the distances between Descendant node pairs. Dynamic programming methods require recursively using DFS to build the root of the tree and calculate the distance from the root to every other node. The result of both methods is the same and consists of the sum of all pairwise shortest paths in the tree. The decision between two algorithms may be based on specific implementation preferences or tree structures, but both algorithms provide efficient solutions.

The above is the detailed content of The sum of all pairs of shortest paths in the tree. For more information, please follow other related articles on the PHP Chinese website!