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

Question

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

Answer 1

There are n nodes.

1. Convert the tree to an undirected graph, and then use n-time single-source shortest path algorithms such as dijkstra and spfa or 1-time floyd multi-source shortest path algorithm to find the values ​​of any two nodes. But when n is relatively large, the memory overhead of storing the value is large.

2. Make the tree a rooted tree, and each node i stores the distance di to the root. When querying two nodes di,dj, find the common ancestor dk of the two nodes, then d(i,j)=di+dj-dk*2. For information on common ancestors, please refer to the Tarjan algorithm.

Answer 2

Consider Floyd’s algorithm as an undirected graph.