What is best (in terms of time complexity) known algorithm (approximate or exact) for finding diameter of a large undirected graph?
The diameter is defined as longest of shortest paths between any two nodes.
I know that naive solution takes O(nm) steps and is basically taking pairs of all vertices and finds distances between them.
This is very slow for large graphs, 2^20 nodes or more.
An example graph