Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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 longest distance between two vertices in graph.

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

share|cite|improve this question
Please elaborate a tad. Why is this problem of interest to you? Do you need a hint, a complete analysis or a reference? Are you interested in worst- or average-case time? Is $G$ directed? –  Raphael Mar 10 '12 at 12:52
@Raphael: Obviously I don't need a hint, I need a complete analysis. I edited my question anyway. –  Gigili Mar 10 '12 at 13:04
@Gigili You mean $\Theta$ in all cases, right? Otherwise, all are subsumed by the last possibility (which is on general graphs equal to $\cal{O}(|V|^5)$) which makes it a correct answer, assuming at least one answer is supposed to be correct. An additional concern is that in a graph with cycles, there is no longest path. What is meant by "longest distance"? –  Raphael Mar 10 '12 at 13:31
@Gigili Where do the four choices come from? –  uli Mar 10 '12 at 13:50

4 Answers 4

up vote 4 down vote accepted


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

enter image description here

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 $v$
  2. Find $u$ such that $d(v,u)$ is maximum
  3. Find $w$ such that $d(u,w)$ is maximum
  4. 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.

share|cite|improve this answer
To mkae Dijsktra work in the time bound specified you need to use Fibonacci heaps, not the usual implementation. –  Suresh Mar 11 '12 at 6:43
This is strongly wrong answer, this algorithm is folklore but in trees not general graphs. P.S: I can see your counter example, but it's not good answer to be marked as answer. –  user742 Apr 2 '12 at 23:15

I assume you mean the diameter of $G$ which is the longest shortest path found in $G$.

Finding the diameter can be done by finding all pair shortest paths first and determining the maximum length found. Floyd-Warshall algorithm does this in $\Theta(|V|^3)$ time. Johnson's algorithm can be implemented to achieve $\cal{O}(|V|^2\log |V| + |V|\cdot|E|)$ time.

A smaller worst-case runtime bound seems hard to achieve as there are $\cal{O}(|V|^2)$ distances to consider and calculating those distance in sublinear (amortised) time each is going to be tough; see here for a related bound. Note this paper which uses a different approach and obtains a (slightly) faster algorithm.

share|cite|improve this answer
If you get paywalled on those papers, check Google Scholar. –  Raphael Mar 10 '12 at 14:12

You can also consider an algebraic graph theoretic approach. The diameter $\text{diam}(G)$ is the least integer $t$ s.t. the matrix $M=I+A$ has the property that all entries of $M^t$ are nonzero. You can find $t$ by $O(\log n)$ iterations of matrix multiplication. The diameter algorithm then requires $O(M(n) \log n)$ time, where $M(n)$ is the bound for matrix multiplication. For example, with the generalization of the Coppersmith-Winograd algorithm by Vassilevska Williams, the diameter algorithm would run in $O(n^{2.3727} \log n)$. For a quick introduction, see Chapter 3 in Fan Chung's book here.

If you restrict your attention to a suitable graph class, you can solve the APSP problem in optimal $O(n^2)$ time. These classes include at least interval graphs, circular arc graphs, permutation graphs, bipartite permutation graphs, strongly chordal graphs, chordal bipartite graphs, distance-hereditary graphs, and dually chordal graphs. For example, see Dragan, F. F. (2005). Estimating all pairs shortest paths in restricted graph families: a unified approach. Journal of Algorithms, 57(1), 1-21 and the references therein.

share|cite|improve this answer
It's worth noting that this algorithm only works in the unweighted case. –  GMB Jan 23 at 13:32

1. Graph is unweighted
2. Graph is directed

O(|V||E|) time complexity.


  if ( isCycle( G(v,E) ) ) then
     return INFINITY
  if ( not isConnected( G(V,E) )) then
     return INFINITY
  diameter = 0
  for each vertex u in G(V,E):
     temp = BFS(G,u)
     diameter = max( temp , diameter )
  return diameter

We check for cycle. if graph contains cycle then we keep in moving in the loop, so we will be having infinite distance. We check for connected. If graph is not connected that means vertex u from G1 to vertex v in G2. Where G1 and G2 is any two sub graph which are not connected. So we will be having infinite distance again. We will use BFS to compute maximum distance between a given node(u) to all others nodes(v) which are reachable from u. Then we will take maximum of previously computed diameter and the result return by BFS. So we will be having current maximum diameter.

Running time analyzing:

  1. O(|E|) using DFS
  2. O(|E|) using DFS
  3. BFS runs in O(|E|) time.
  4. We have to call BFS function for each vertex so total it will take O(|V||E|) time.

Total time = O(|v||E|) + O(|E|) + O(|E|)
Since |V||E| > |E|
so we have running time as O(|v||E|).


Note: This not an elegant solution to this problem.

share|cite|improve this answer
Acyclic connected graphs are trees, for which the problem is easier (because the diameter is then given by the longest path). It has been dealt with here and here, where faster algorithms are given. (One recursive traversal or, alterlative, two BFS are sufficient.) –  Raphael Sep 10 at 9:08
@Raphael No, acyclic undirected graphs are trees. DAGs are DAGs. –  David Richerby Sep 10 at 13:00
@DavidRicherby Right. (Although, technically, the answer doesn't say if it excludes directed or undirected cycles. ;)) Anyway, this is nothing but solving APSPP (the naive approach), which has already been covered for the general case by previous answers. –  Raphael Sep 10 at 13:02
@Raphael Are you sure Acyclic graphs are trees ? Graph is Acyclic doesn't mean that graph will be always tree. Tree is just a special case of this.Also this is straight forward algorithm and time complexity is O(|V||E|). –  sonu kumar Sep 10 at 17:46

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.