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

问题描述

问 题

每个节点的数据结构是一个value ，和这个节点的所有子节点

解决方案

设有n个节点。

1. 树转无向图，然后用n次dijkstra、spfa等单源最短路算法或1次floyd多源最短路算法求任意两节点的值。但是当n比较大的话储存值对内存的开销较大。

2. 使树成为有根树，每个节点i储存到根的距离di。查询两节点di,dj时，求两节点的公共祖先dk，则d(i,j)=di+dj-dk*2。关于公共祖先可以参考tarjan算法。

这篇关于java - 如何求多叉树两个任意节点的最短路径呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！