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?

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

Solution 2

For a general Graph G=(V,E) there is no O(log V * (V + E)) time complexity algorithm known for computing the diameter. The current best solution is O(V*V*V), e.g., by computing all shortest Paths with Floyd Warshall's Algorithm. For sparse Graphs, i.e. when E is in o(N*N), Johnson's Algorithm gives you with O(V*V*log(V)+V*E) a better time complexity.

If your graph has certain properties like acyclic (Tree) you can get better.

So the bad news is, the Dijkstra won't be enough in the general case...

Solution 3

As eci mentioned, one of the solutions is to use the Floyd-Warshall algorithm. If you need the code for it, a C++ version of it can be found here.

Solution 4

Graph description - undirected and unweighted, n nodes, m edges For the diameter of the graph, we need to calculate the shortest path between all pairs of nodes. Shortest paths between a source node to all other nodes can be calculated using the BFS algorithm for an undirected and unweighted graph. Time complexity is O(n + m) for 1 node. Here since we need to do a BFS for n nodes, the total time complexity of finding the shortest path between all pairs of nodes becomes O(n(n + m)). Since there are n(n-1)/2 pairs of nodes, so we have n(n-1)/2 values of the shortest path between all the nodes. For the diameter, we need to get the max of these values, which is again O(n*n). So the final time complexity becomes:

       O(n(n + m)) + O(n*n) = O(n(2n + m)) = O(n(n + m))

Pseudocode for getting the shortest paths between all pairs of nodes. We are using a matrix named Shortest_paths to store the shortest paths between any two pair of nodes. We are using a dictionary named flag which has values true or false which indicates whether the vertex has been visited or not. For each iteration of BFS, we initialize this dictionary to all false. We use a Queue Q to perform our BFS. Algorithm BFS(for all nodes)

Initialize a matrix named Shortest_paths[n][n] to all -1. 
    For each source vertex s
        For each vertex v
            Flag[v] = false
        Q = empty Queue
        Flag[s] = true
        enQueue(Q,s)
        Shortest_paths[s][s] = 0
        While Queue is not empty
            Do v = Dequeue(Q)
            For each w adjacent to v
                Do if flag[w] = false
                    Flag[w] = true
                    Shortest_paths[s][w] = Shortest_paths[s][v] + 1
                    enQueue(Q,w) 
    Diameter = max(Shortest_paths)
    Return Diameter

Solution 5

Assuming that the graph is unweighted then the following steps can find the solution in O(V * ( V + E )) where V is the number of vertices and E is the number of edges.

Let's define the distance between 2 vertices u, v to be the length of shortest path between u and v. Denote it by d(u, v) Define Eccentricity of a vertex v to be e(v) = max {d(u, v) | u ∈ V(G)} (V(G) is the set of vertices in graph G) Define Diameter(G) = max{e(v) | v ∈ V(G)}

Now to the algorithm:

1- For each vertex v in V(G) run BFS(v) and build a 2 dimensional array of distances from each vertex to others. (calculating the distance from each vertex to others is easy to do in the BFS algorithm)

2- Compute e(v) for each vertex from the 2 dimensional array created in step 1 3- compute diameter(G) by finding the maximum e(v) from step 2

Now to analyze this algorithm, it's easy to see that it's dominated by the first step which is of O (V * (V + E))

Read this part about diameter in Wikipedia

Another algorithm that runs in linear time O(V + E) 1- Run BFS on any random vertex v ∈ V(G) 2- Pick the vertex u with maximum distance 3- Run BFS again on that vertex u 4- Diameter is the maximum distance generated form step 3

View more solutions

Comments

[eci]

I think the question was related to an abstract graph. Your answer relates to a number of points in the plain and to find the maximum distance between them, which is not the same. For example, the abstract graph does not have to meet the triangle inequality. Also, the total order of your algorithm will be O(nh+hh) which is less then O(nh^3).

[Jan Hudec]

BFS definitely does not work in o(v + e) (what are v and e anyway?). O(V + E) yes. But then Dijkstra's algorithm is also O(V + E) and works on weighted graphs, so there is no difference. And remember there is still V vertices, so how do you expect to reduce it to the log(V) factor? (-1)

[Ankit Roy]

Nice approach. A few minor points: (1) I think that there can still be zero entries in B after i reaches 0, and in that case the diameter is 2^K (i.e. the original squaring loop happened to find the smallest diameter). (2) You could use bitwise AND and OR instead of multiplication and addition respectively to ensure that cell values don't get unwieldy. (3) After log2(n) squarings of the adjacency matrix, either all entries are nonzero or the graph was not connected in the first place.

[Mehmet Fide]

can you provide a simple example about how to use it?

[Admin]

the second one finds pseudo-peripheral vertices, not necessarily peripheral ones.