93 views

The diameter of a tree $T= (V, E)$ is defined as $max_{u,v\ \epsilon\ V}\ \delta(u,v)$, that is, the largest of all shortest-path distances in the tree. Give an efficient algorithm to compute the diameter of a tree, and analyze the running time of your algorithm.

| 93 views

we can use Floyd-Warshall Algortihm to calculate the shortest distance between every pair of vertices and then find the maximum.

so, the time complexity would be O(n^3)

Space Complexity is O(n^2).
by Junior (725 points)
edited ago