文章详情页
java - 如何求多叉树两个任意节点的最短路径呢？
浏览：209日期：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. docker start -a dockername 老是卡住，什么情况？2. java内存模型的happens-before语义顺序问题3. java - 并发操作下关于队列的疑问？4. 编程 - java 为什么没有静态方法接口，有没有哪门语言有静态方法接口。5. objective-c - iOS开发使用什么对html进行代码高亮6. linux - 阿里云服务器（centos）中svn同步web目录的问题？7. android - as添加依赖时一直是gradle:download状态8. ：not 选择器 无效果 原因何在？9. 数据库 - Mysql的存储过程真的是个坑！求助下面的存储过程哪里错啦，实在是找不到哪里的问题了。10. mysql插入文本如果是个sql语句就报错了
排行榜
网公网安备