文章详情页

java - 如何求多叉树两个任意节点的最短路径呢？

浏览：144日期：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

上一条：java - 一个类的对象锁只有一个，类锁呢？下一条：java - c++学习数据结构应不应该用stl实现？

相关文章：

1. java - 在session里面设了一个对象，但是在Jsp中取不到2. docker - 各位电脑上有多少个容器啊？容器一多，自己都搞混了，咋办呢？3. 为什么我ping不通我的docker容器呢？？？4. boot2docker无法启动5. 咨询下jq的问题6. debian - docker依赖的aufs-tools源码哪里可以找到啊？7. docker不显示端口映射呢？8. mysql里的大表用mycat做水平拆分，是不是要先手动分好，再配置mycat9. python redis 列表插入速度太慢10. docker内创建jenkins访问另一个容器下的服务器问题

排行榜

					
					java - 在session里面设了一个对象，但是在Jsp中取不到
为什么我ping不通我的docker容器呢？？？
docker - 各位电脑上有多少个容器啊？容器一多，自己都搞混了，咋办呢？
关于docker下的nginx压力测试
咨询下jq的问题
在windows下安装docker  Toolbox 启动Docker Quickstart Terminal 失败！
docker内创建jenkins访问另一个容器下的服务器问题
docker不显示端口映射呢？
debian - docker依赖的aufs-tools源码哪里可以找到啊？
golang - 用IDE看docker源码时的小问题
docker images显示的镜像过多，狗眼被亮瞎了，怎么办？
				

热门标签