文章详情页
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. javascript - 静态页面引公共头尾文件，js怎么写吖？2. css - 手机端chrome打开github和bilibili等少数网站会发现地址栏周围也会有背景色3. java - 3个dao的数据根据请求参数选择一个映射到一个url上，怎么写比较好?4. javascript - 读取页面源码，页面中所有的换行都被当成<br/>读取出来 了，，求解应该怎么让它被正确的解析5. java - Spring使用@Autowired失效但是getBean()可以执行成功6. javascript - 关于一段 for 循环代码执行顺序的问题7. docker 17.03 怎么配置 registry mirror ?8. html5 - 百度Ueditor代码高亮和代码段滚动条冲突是怎么回事?9. docker网络端口映射，没有方便点的操作方法么？10. 求解答：访问不了虚拟服务器的问题？
排行榜
网公网安备