文章详情页
java - 如何求多叉树两个任意节点的最短路径呢？
浏览：92日期：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. 微信小程序如何加载h5页面2. MYSQL代码执行错误：FUNCTION any_value does not exist3. 阿里云服务器mysql中文乱码4. python - 如何解决程序运行太久之后被操作系统暂停的情况？5. javascript - react如何获取offsetX？6. javascript - antDesign的table column最后一次加载的时候this是undefined 怎么回事7. mysql - oracle物化视图和临时表的区别是什么？8. sort - javascript 手动指定对象阵列的顺序9. 网页爬虫 - python+requests 网页重定向求解10. node.js - nodejs开发中常用的连接mysql的库
排行榜
网公网安备