文章详情页
java - 如何求多叉树两个任意节点的最短路径呢？
浏览：180日期：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. mysql - 在不允许改动数据表的情况下，如何优化以varchar格式存储的时间的比较？2. css - chrome下a标签嵌套img 显示会多个小箭头?3. javascript - 网页打印页另存为pdf的代码一个问题4. vim - docker中新的ubuntu12.04镜像,运行vi提示,找不到命名.5. java中返回一个对象，和输出对像的值，意义在哪儿6. css3 - 纯css实现点击特效7. docker网络端口映射，没有方便点的操作方法么？8. mysql 为什么主键 id 和 pid 都市索引, id > 10 走索引 time > 10 不走索引?9. javascript - Img.complete和img.onload判断图片加载完成有什么区别？10. javascript - 有适合开发手机端Html5网页小游戏的前端框架吗？
排行榜
网公网安备