树中所有对最短路径之和

在树中，“所有节点对最短路径之和”的术语指的是计算所有节点对的个别最短路径的总和。一种有效的方法是使用双重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中文网其他相关文章！