文章详情页
java - 如何求多叉树两个任意节点的最短路径呢？
浏览：319日期：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容器呢SSH为什么连不通呢？2. Docker for Mac 创建的dnsmasq容器连不上/不工作的问题3. golang - 用IDE看docker源码时的小问题4. docker images显示的镜像过多，狗眼被亮瞎了，怎么办？5. docker start -a dockername 老是卡住，什么情况？6. Hbuilder中的phpMyAdmin访问题7. 前端 - 类到底该如何去命名 .newsList 这种的命名难道真的不是过度语义化吗？~8. 如何解决Centos下Docker服务启动无响应，且输入docker命令无响应？9. docker api 开发的端口怎么获取？10. javascript - 关于用户登录和信息存储的问题
排行榜
网公网安备