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.
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.
![[Web front-end] Permulaan pantas Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
Terdapat n nod.
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.
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.
Pertimbangkan algoritma Floyd sebagai graf tidak terarah.