# What is a best known algorithm for finding diameter of undirected graph? [duplicate]

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

http://snap.stanford.edu/data/com-Orkut.html

• Especially when you also care about approximate methods, best in what sense?
– Juho
Jan 14, 2015 at 18:45
• Best in terms of time complexity Jan 14, 2015 at 19:01
• If you're willing to settle for a 2-approximation, you can run BFS from an arbitrary node. Jan 14, 2015 at 20:56
• How would 2 approximation work in this case? Looks like it would give different answer in each case. Jan 14, 2015 at 21:39
• @RB It is a worst-case 2-approximation. It will return a value between the actual diameter and 2x the actual diameter. Jan 15, 2015 at 9:20