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

Question

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

Answer 1

n 個のノードがあります。

1. ツリーを無向グラフに変換し、ダイクストラや spfa などの n 回単一ソース最短パス アルゴリズム、または 1 回フロイド マルチソース最短パス アルゴリズムを使用して、任意の 2 つのノードの値を見つけます。ただし、n が比較的大きい場合、値を保存する際のメモリ オーバーヘッドが大きくなります。

2. ツリーをルート付きツリーにし、各ノード i にルートまでの距離 di を保存します。 2 つのノード di,dj をクエリする場合、2 つのノードの共通の祖先 dk を見つけ、d(i,j)=di+dj-dk*2 となります。共通の祖先については、Tarjan アルゴリズムを参照してください。

Answer 2

フロイドのアルゴリズムを無向グラフとして考えてみましょう。