# The time complexity of finding the diameter of a graph

What is the time complexity of finding the diameter of a graph
$G=(V,E)$?

• ${O}(|V|^2)$
• ${O}(|V|^2+|V| \cdot |E|)$
• ${O}(|V|^2\cdot |E|)$
• ${O}(|V|\cdot |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.

### 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 $$vv$$): 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:

1. Pick a vertex $$vv$$
2. Find $$uu$$ such that $$d(v,u)d(v,u)$$ is maximum
3. Find $$ww$$ such that $$d(u,w)d(u,w)$$ is maximum
4. Return $$d(u,w)d(u,w)$$

Its complexity is the same as two successive breadth first searches¹, that is $$O(|E|)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|)O(|E|+|V|\log|V|)$$ but I am only sure about $$O(|E|log|V|)O(|E|\log|V|)$$.

² If the graph is not connected you get $$O(|V|+|E|)O(|V|+|E|)$$ but you may have to add $$O(α(|V|))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.