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

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

浏览：111日期：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 api 开发的端口怎么获取？2. javascript - vue-cli怎么根据后端接口服务器不同 build不同接口代码？3. angular.js - angular2 有什么cool的loading组件么？4. mysql 一个sql 返回多个总数5. angular.js - angularjs中的$compile怎么理解？6. 从Spring MVC XML文件移至javaconfig我的数据库XML文件真的让我迷茫了7. java - SpringBoot 添加自定义的拦截器，却不调用8. ubuntu - elasticsearch－head插件安装后，启动问题！9. javascript - 前端开发 本地静态文件频繁修改，预览时的缓存怎么解决？10. angular.js - angularjs ng-class指令改变ng-click点击的class属性失效
排行榜
java - SpringBoot 添加自定义的拦截器，却不调用
java - SpringBoot 添加自定义的拦截器，却不调用
1. javascript - 前端开发 本地静态文件频繁修改，预览时的缓存怎么解决？
2. 从Spring MVC XML文件移至javaconfig我的数据库XML文件真的让我迷茫了
3. ubuntu - elasticsearch－head插件安装后，启动问题！
4. 关于docker下的nginx压力测试
5. docker api 开发的端口怎么获取？
6. angular.js - angularjs中的$compile怎么理解？
7. mysql 一个sql 返回多个总数
8. angular.js - angular2 有什么cool的loading组件么？
9. javascript - vue-cli怎么根据后端接口服务器不同 build不同接口代码？
10. angular.js - angularjs ng-class指令改变ng-click点击的class属性失效
热门标签