# Developers Planet

Walter February 2016

### Algorithm for diameter of graph

I have heard of algorithm of finding diameter of graph using the following algorithm:

``````Algorithm (start_vertex):
find out the set of vertices S having maximum value of
shortest distance from start_vertex.
ans = 0;
for each vertex v in S
temp = 0;
for each vertex u in graph G:
temp = max(temp, shortest distance between u and v).
ans = temp;
return ans;
``````

The following algorithm fails several times: for example when n=7 we can draw the following graph:

``````1 2
1 3
2 4
3 4
2 6
2 7
4 5
``````

With start_vertex=1 ,this algorithm gives shortest path as 3 but the answer is 4. Can someone give the general case when does this algorithm fails.Also tell me whether this will work for n=8 where n is the no of vertices of the graph

Aviral Kumar February 2016

No the answer should be 3 in this case.. It doesn't fail here

kobe24 February 2016

This is a problem from a running contest, it would be better if you ask this question after the contest ends.