您的位置：首页技术文章
文章详情页

java - 如何求多叉树两个任意节点的最短路径呢？

浏览：202日期：2024-02-02 11:31:00

问题描述

每个节点的数据结构是一个value ，和这个节点的所有子节点

问题解答

回答1：

设有n个节点。

树转无向图，然后用n次dijkstra、spfa等单源最短路算法或1次floyd多源最短路算法求任意两节点的值。但是当n比较大的话储存值对内存的开销较大。

使树成为有根树，每个节点i储存到根的距离di。查询两节点di,dj时，求两节点的公共祖先dk，则d(i,j)=di+dj-dk*2。关于公共祖先可以参考tarjan算法。

回答2：

当成无向图考虑Floyd算法.

标签： java
上一条：java - 一个类的对象锁只有一个，类锁呢？下一条：java - c++学习数据结构应不应该用stl实现？
相关文章：
1. docker gitlab 如何git clone？2. docker-compose 为何找不到配置文件？3. docker images显示的镜像过多，狗眼被亮瞎了，怎么办？4. docker不显示端口映射呢？5. dockerfile - [docker build image失败- npm install]6. docker内创建jenkins访问另一个容器下的服务器问题7. angular.js - 如何从AngularJS迁移到Vue？8. docker 17.03 怎么配置 registry mirror ?9. docker 下面创建的IMAGE 他们的 ID 一样？这个是怎么回事？？？？10. javascript - 如何申请blog.xxx.com 这种二级域名？
排行榜
docker gitlab 如何git clone？
docker gitlab 如何git clone？
1. dockerfile - [docker build image失败- npm install]
2. docker images显示的镜像过多，狗眼被亮瞎了，怎么办？
3. docker不显示端口映射呢？
4. docker-compose 为何找不到配置文件？
5. docker内创建jenkins访问另一个容器下的服务器问题
6. angular.js - 如何从AngularJS迁移到Vue？
7. docker 17.03 怎么配置 registry mirror ?
8. docker 下面创建的IMAGE 他们的 ID 一样？这个是怎么回事？？？？
9. angular.js - 只有用#，angularjs和vuejs的路由才能识别路径？
10. python django工程上传一张照片调用python方法时报错，请问如何处理？
热门标签