Algorithm for diameter of graph?

omega picture omega · Mar 26, 2013 · Viewed 35.7k times · Source

If you have a graph, and need to find the diameter of it (which is the maximum distance between two nodes), how can you do it in O(log v * (v + e)) complexity.

Wikipedia says you can do this using Dijkstra's algorithm with a binary heap. But I don't understand how this works. Can someone explain please?

Or show a pseudocode?

Answer

GMB picture GMB · Jan 23, 2015

I know I'm a year late to the thread, but I don't believe any of these answers are correct. OP mentioned in the comments that the edges are unweighted; in this case, the best algorithm runs in O(nω log n) time (where ω is the exponent for matrix multiplication; currently upper bounded at 2.373 by Virginia Williams).

The algorithm exploits the following property of unweighted graphs. Let A be the adjacency matrix of the graph with an added self-loop for each node. Then (Ak)ij is nonzero iff d(i, j) ≤ k. We can use this fact to find the graph diameter by computing log n values of Ak.

Here's how the algorithm works: let A be the adjacency matrix of the graph with an added self loop for each node. Set M0 = A. While Mk contains at least one zero, compute Mk+1 = Mk2.

Eventually, you find a matrix MK with all nonzero entries. We know that K ≤ log n by the property discussed above; therefore, we have performed matrix multiplication only O(log n) times so far. We can now continue by binary searching between MK = A2K and MK-1 = A2K-1. Set B = MK-1 as follows.

Set DIAMETER = 2k-1. For i = (K-2 ... 0), perform the following test:

Multiply B by Mi and check the resulting matrix for zeroes. If we find any zeroes, then set B to this matrix product, and add 2i to DIAMETER. Otherwise, do nothing.

Finally, return DIAMETER.

As a minor implementation detail, it might be necessary to set all nonzero entries in a matrix to 1 after each matrix multiplication is performed, so that the values don't get too large and unwieldy to write down in a small amount of time.