文章详情页
java - 如何求多叉树两个任意节点的最短路径呢？
问题描述
每个节点的数据结构是一个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. 引用 node.js express加载 静态文件 报错 ??2. javascript - 引入 simditor，但是显示标签，这个怎么解决。3. 如何更新/删除指定的两条或多条数据4. 优先级的问题？5. android - 目前有哪些用Vue.js开发移动App的方案？6. 搭建一个用户间相互博弈的网站7. mysql_replication - mysql读写分离时如果单台写库也无法满足性能怎么解决8. node.js - 利用vue-cli 构建执行到npm run dev 报错，求解~9. mysql 一个sql 返回多个总数10. vue.js - weex 没有背景图片属性怎么办？
排行榜
网公网安备