文章详情页
java - 如何求多叉树两个任意节点的最短路径呢？
浏览：299日期：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. javascript - [MUI 子webview定位]2. docker绑定了nginx端口 外部访问不到3. docker - 各位电脑上有多少个容器啊？容器一多，自己都搞混了，咋办呢？4. 前端 - 怎样让scale缩小的元素不占据原来的空间？5. dockerfile - 为什么docker容器启动不了？6. angular.js使用$resource服务把数据存入mongodb的问题。7. javascript - 新组成的数组打印出来出现问题，里面有对象，但长度为空8. macos - mac下docker如何设置代理9. javascript - Js对象怎么通过value值拿到key值？10. vue.js - Vue APP基于webpack的项目，它是独立的项目吗？我后台是Java的，要如何实现，跨域请求吗？大牛请教一下谢谢
排行榜
网公网安备