What is the time complexity of finding the diameter of a graph

G=(V,E)?

- O(|V|2)
- O(|V|2+|V|⋅|E|)
- O(|V|2⋅|E|)
- O(|V|⋅|E|2)
The diameter of a graph G is the maximum of the set of shortest path distances between all pairs of vertices in a graph.

I have no idea what to do about it, I need a complete analysis on how to solve a problem like this.

**Answer**

### Update:

**This solution is not correct.**

The solution is unfortunately only true (and straightforward) for trees! Finding the diameter of a tree does not even need this. Here is a counterexample for graphs (diameter is 4, the algorithm returns 3 if you pick this v):

If the graph is directed this is rather complex, here is some paper claiming faster results in the dense case than using algorithms for all-pairs shortest paths.

However my main point is about the case the graph is *not* directed and with non-negative weigths, I heard of a nice trick several times:

- Pick a vertex v
- Find u such that d(v,u) is maximum
- Find w such that d(u,w) is maximum
- Return d(u,w)

Its complexity is the same as two successive breadth first searches¹, that is O(|E|) if the graph is connected².

It seemed folklore but right now, I’m still struggling to get a reference *or* to prove its correction. I’ll update when I’ll achieve one of these goals. It seems so simple I post my answer right now, maybe someone will get it faster.

¹ if the graph is weighted, wikipedia seems to say O(|E|+|V|log|V|) but I am only sure about O(|E|log|V|).

² If the graph is not connected you get O(|V|+|E|) but you may have to add O(α(|V|)) to pick one element from each connected component. I’m not sure if this is necessary and anyway, you may decide that the diameter is infinite in this case.

**Attribution***Source : Link , Question Author : Gigili , Answer Author : Community*