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

Question

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

Answer 1

n개의 노드가 있습니다.

1. 트리를 무방향 그래프로 변환한 후 dijkstra, spfa 등 n회 단일 소스 최단 경로 알고리즘이나 1회 플로이드 다중 소스 최단 경로 알고리즘을 사용하여 임의의 값을 찾습니다. 두 개의 노드. 그러나 n이 상대적으로 크면 값을 저장하는 메모리 오버헤드가 커집니다.

2. 트리를 뿌리가 있는 트리로 만들고, 각 노드 i는 루트까지의 거리 di를 저장합니다. 두 노드 di,dj를 쿼리할 때 두 노드의 공통 조상 dk를 찾은 다음 d(i,j)=di+dj-dk*2를 찾습니다. 공통 조상에 대한 정보는 Tarjan 알고리즘을 참조하세요.

Answer 2

플로이드의 알고리즘을 무방향 그래프로 생각해보세요.