文章详情页
java - 如何求多叉树两个任意节点的最短路径呢？
浏览：167日期：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. php - 第三方支付平台在很短时间内多次异步通知,订单多次确认收款2. html5 - h5写的app用的webview，用手机浏览器打开不显示？3. css3 - css before 中文乱码？4. mysql新建字段时 timestamp NOT NULL DEFAULT ’0000-00-00 00:00:00’ 报错5. javascript - 百度echarts series数据更新问题6. Mysql && Redis 并发问题7. css - 求推荐几款好用的移动端页面布局调试工具呢？8. mysql - 一个表和多个表是多对多的关系，该怎么设计9. javascript - webpack --hot 热重载无效的问题10. javascript - node服务端渲染的困惑
排行榜
网公网安备