Algorithm for diameter of graph?

Question

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 1

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 (A^k)_ij is nonzero iff d(i, j) ≤ k. We can use this fact to find the graph diameter by computing log n values of A^k.

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

Eventually, you find a matrix M_K 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 M_K = A^2K and M_K-1 = A^2K-1. Set B = M_K-1 as follows.

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

Multiply B by M_i and check the resulting matrix for zeroes. If we find any zeroes, then set B to this matrix product, and add 2ⁱ 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.