My question on Stack Overflow was recently tagged "math". Despite a bounty, it never received a satisfactory answer, so I thought I would ask it here:

I have a large, connected, sparse graph in adjacency-list form. I would like to find the diameter of the graph and two vertices achieving it.

**Is there a better approach than computing all-pairs shortest paths?**

I am interested in this problem in both the undirected and directed cases, for different applications. In the directed case, I of course care about directed distance (the maximum over pairs of vertices of the length of the shortest directed path from the first vertex to the second).

essentiallyruns the Bellman–Ford algorithm in time O(V^3). Their "non-matrix methods" sections runs Dijktra for each vertex, which is Johnson's algorithm at O(V^2 log V + VE). However, they combine this with an upper bound for the diameter, obtained from the diameter of the minimum spanning tree (which can be computed quite efficiently). Unfortunately, if their bound is not met (and they have no reason to believe it will be), their suggestion is simply Johnson's algorithm for all-pairs shortest paths. $\endgroup$ – aorq Jan 11 '10 at 17:17