树中所有对最短路径之和

老丽酱_8700

老丽酱_8700

2023-08-28

964人浏览

转载

树中所有对最短路径之和

在树中,“所有节点对最短路径之和”的术语指的是计算所有节点对的个别最短路径的总和。一种有效的方法是使用双重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 <h3>输出</h3>
<pre class="brush:php;toolbar:false;">Total sum of distances between descendants of the LCA: 0

动态规划方法:

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

Trae Solo
Trae Solo

一款AI开发辅助工具,主要用于字节旗下Trae推出的独立AI编程智能体工具,适合需要提升相关任务效率的用户。

下载

算法

  • 将树中的任何节点作为根并以树为根(例如,使用根节点的深度搜索)以创建有根树。

  • 动态规划可用于确定每个节点距根的距离。这些距离应该存储在数组或数据结构中。

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

  • 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 <h3>输出</h3>
<pre class="brush:php;toolbar:false;">Sum of all pair shortest paths in the tree: 0

结论

树中所有对最短路径的总和可以使用 Double DFS(深度优先搜索)方法或动态规划来计算。 Double DFS 方法由两遍组成,首先计算从选定节点到所有其他节点的距离,然后再次遍历树,同时将每个节点视为潜在的最低公共祖先 (LCA),以将之间的距离相加后代节点对。动态规划方法需要递归地使用 DFS 来建立树的根并计算从根到每个其他节点的距离。两种方法的结果是相同的,并且由树中所有成对最短路径的总和组成。两种算法之间的决策可能基于特定的实现偏好或树结构,但两种算法都提供了有效的解决方案。

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

120

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

100

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

60

15

Postman身份认证怎么配置
Postman身份认证怎么配置

本专题从实际API接口调试场景出发,讲解Postman身份认证的完整配置流程,包括常见认证协议介绍、授权参数设置、访问令牌填写、OAuth 2.0授权及认证失败排查,帮助用户正确完成接口授权与访问验证。

2026.11.06

160

12

Postman请求头Headers怎么设置
Postman请求头Headers怎么设置

围绕Postman HTTP请求头配置展开,讲解Headers选项的具体使用方式,包括Key和Value参数填写、请求头信息添加、常见Header字段设置及请求头修改方法,帮助用户解决接口调试过程中遇到的请求头配置问题。

2026.11.06

140

13

Postman接口请求发送教程
Postman接口请求发送教程

详细介绍Postman接口请求的创建与发送方法,涵盖GET和POST请求、URL配置、请求参数、Headers请求头、Body请求体设置以及响应结果查看,帮助用户掌握Postman接口请求的完整操作流程。

2026.11.06

120

10

DBeaver怎么导入数据
DBeaver怎么导入数据

DBeaver数据导入专题,整理Excel、CSV、SQL、TXT等常见文件的数据导入方法,涵盖目标数据库选择、数据表创建、字段映射、数据类型设置及导入参数配置等操作,帮助用户将本地文件中的数据写入数据库,并了解批量导入、重复数据处理和导入失败等常见问题的解决方法。

2026.11.05

100

12

DBeaver安全防护教程大全
DBeaver安全防护教程大全

DBeaver安全防护专题,围绕数据库连接安全、账号密码保护和访问权限管理展开,整理SSL/TLS加密连接、SSH隧道、数据库凭据保存及证书验证等配置方法,同时介绍敏感信息保护、远程连接风险和高权限账号使用等注意事项,帮助用户提高数据库日常管理的安全性。

2026.11.05

100

12

DBeaver连接创建与配置教程
DBeaver连接创建与配置教程

本专题聚焦DBeaver数据库连接配置与管理,覆盖从新建连接、选择数据库类型到填写连接参数和验证连接的完整流程。针对MySQL、PostgreSQL、SQL Server等常见数据库,整理相应的连接设置方法,并提供驱动缺失、认证失败和连接异常等问题的排查方向。

2026.11.04

100

16

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
swoole进程树解析
swoole进程树解析

共4课时 | 0.3万人学习

HTML DOM中文参考手册
HTML DOM中文参考手册

共14课时 | 10.3万人学习