文章详情页
java - 如何求多叉树两个任意节点的最短路径呢？
浏览：173日期：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
相关文章：
1. javascript - 如何让移动端网页的输入框固定在底部？2. angular.js - angularjs的自定义过滤器如何给文字加颜色？3. docker镜像push报错4. angular.js - angular内容过长展开收起效果5. 请教各位大佬，浏览器点 提交实例为什么没有反应6. MySQL中无法修改字段名的疑问7. linux - 升级到Python3.6后GDB无法正常运行?8. 大家好，请问在python脚本中怎么用virtualenv激活指定的环境？9. 网页爬虫 - 用Python3的requests库模拟登陆Bilibili总是提示验证码错误怎么办?10. 并发模型 - python将进程池放在装饰器里为什么不生效也没报错
排行榜
网公网安备