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

Question

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

Answer 1

設有n個節點。

1. 樹轉無向圖，再用n次dijkstra、spfa等單源最短路演算法或1次floyd多源最短路演算法求任兩節點的值。但是當n比較大的話儲存值對記憶體的開銷較大。

2. 使樹成為有根樹，每個節點i儲存到根的距離di。查詢兩節點di,dj時，求兩個節點的公共祖先dk，則d(i,j)=di+dj-dk*2。關於公共祖先可以參考tarjan演算法。

Answer 2

當成無向圖考慮Floyd演算法.