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