diameter of a graph

Question

FINDING diameter of a graph-

i could think of 2 options for finding diameter-

1) running BFS from each vertex and then finding longest among then

2) computing all pair shortest paths (by floyd warshall) and then finding longest among them

is there any other method or algo?can DFS be used to find diameter?

please suggest.

Comments

I think for general graph this problem can be solved by dynamic programming. It will take each case.

---

bhai, dynamic prog. can solve every type of problem on this earth which is possible via code apart from the prob. where we apply machine learning algo. it is just the time boundation and efficiency that decdide which one we will pick.

---

I have implemented using DFS for a graph ( may contain cycles or not ).

I checked for the following graph:

Now, it gave wrong max diameter for vertex 2 . It was supposd to have 1-3, 2-3, 2-4 edges but included 2-3, 1-3, 3-4 edges instead and counted max diameter as 2.

But, vertices 4 and 1 should have same set of edges for considering max diameter viz. 1-3, 2-3, 2-4 and it considered that  correctly.

So, I think that if there more than 1 vertces having the same set of edges for max diameter, then it may give wrong max diameter fr one of them but correct for one or all of others.

---

---

1) Source file

2) Input and output for above specified diagram

@Debashish @Rahul and all. Could you check on your custom inputs?