The Gateway to Computer Science Excellence
0 votes
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.

in Algorithms by Active (4.4k points) | 93 views

1 Answer

0 votes
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 by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,378 answers
198,523 comments
105,317 users