# 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.

• 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

### 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:

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.

• 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 have two questions about the wrong solution. 1. Would this at least give a range in which the correct answer must be? e.g. if the method finds diameter d, will the correct solution be between d and 2d? 2. What happens if we add another indirection and consider all nodes found by an indirection (not just one)? The counter example given in the post would work then, as true peripheral vertices are among the nodes found by the second indirection. – mafu Dec 5 '17 at 14:17

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.

• If you get paywalled on those papers, check Google Scholar. – Raphael Mar 10 '12 at 14:12
• Also, this exception is worth noting for undirected trees, where you can get dia. with just one dfs traversal. – azam Jan 22 '16 at 6:43

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.

• It's worth noting that this algorithm only works in the unweighted case. – GMB Jan 23 '15 at 13:32

Assumptions:
1. Graph is unweighted
2. Graph is directed

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

Algorithm:

ComputeDiameter(G(V,E)):
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


Explanation:
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.

• 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 '15 at 9:08
• @Raphael No, acyclic undirected graphs are trees. DAGs are DAGs. – David Richerby Sep 10 '15 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 '15 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|). – sonus21 Sep 10 '15 at 17:46
• Yes, I'm sure. (Maybe you are thinking of rooted trees, which are a different flavor.) – Raphael Jan 19 '16 at 10:41