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.
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.
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
There are n nodes.
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.
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.
Consider Floyd’s algorithm as an undirected graph.