文章详情页
java - 如何求多叉树两个任意节点的最短路径呢？
浏览：291日期：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. python 如何打印bytes以16进制输出2. vue.js - 为什么我的vue项目上传到github不能预览？3. javascript - 手机网页如何，插入地图 ；并设置多个标注点 ，还可路线查询4. thinkphp6中怎么把类放到容器中？5. 怎么学好php6. node.js - 我是一个做前端的，求教如何学习vue，node等js引擎？7. javascript - Ajax加载Json时，移动端页面向左上角缩小一截儿，加载完成后才正常显示，这该如何解决？8. mysql - 把一个表中的数据count更新到另一个表里?9. 现在的视频 “多杂乱”10. 如何将行内块元素的内容垂直水平两个方向居中？
排行榜
网公网安备