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

Question

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

Answer 1

Il y a n nœuds.

1. Convertissez l'arbre en un graphe non orienté, puis utilisez des algorithmes de chemin le plus court à source unique n fois tels que dijkstra et spfa ou l'algorithme de chemin le plus court multi-source 1-time floyd pour trouver les valeurs de n'importe quel deux nœuds. Mais lorsque n est relativement grand, la surcharge mémoire liée au stockage de la valeur est importante.

2. Faites de l'arbre un arbre enraciné, et chaque nœud i stocke la distance di à la racine. Lors de l'interrogation de deux nœuds di,dj, recherchez l'ancêtre commun dk des deux nœuds, puis d(i,j)=di+dj-dk*2. Pour plus d'informations sur les ancêtres communs, veuillez vous référer à l'algorithme de Tarjan.

Answer 2

Considérez l'algorithme de Floyd comme un graphe non orienté.