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
But I don't understand how this works. Can someone explain please?
Or show a pseudocode?
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...