Algorithm for diameter of graph?


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?


Answers:


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