Home Ask Login Register

Developers Planet

Your answer is one click away!

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.

Post Status

Asked in February 2016
Viewed 1,200 times
Voted 8
Answered 2 times


Leave an answer

Quote of the day: live life