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

Question

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

Answer 1

Terdapat n nod.

1. Tukar pepohon kepada graf tidak terarah, dan kemudian gunakan algoritma laluan terpendek sumber tunggal n-masa seperti dijkstra dan spfa atau algoritma laluan terpendek berbilang sumber floyd 1 kali untuk mencari nilai mana-mana dua nod. Tetapi apabila n agak besar, overhed memori untuk menyimpan nilai adalah besar.

2. Jadikan pokok sebagai pokok berakar, dan setiap nod i menyimpan jarak di ke akar. Apabila menanyakan dua nod di,dj, cari dk moyang sepunya bagi kedua-dua nod itu, kemudian d(i,j)=di+dj-dk*2. Untuk maklumat tentang nenek moyang yang sama, sila rujuk algoritma Tarjan.

Answer 2

Pertimbangkan algoritma Floyd sebagai graf tidak terarah.