Good algorithm for finding the diameter of a (sparse) graph? 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).
 A: It's only helpful in the dense case, not the sparse case that you're asking about, but Yuster has recently shown that the diameter of an unweighted directed graph can in fact be computed more efficiently than known algorithms for all pairs shortest paths. See his paper "Computing the diameter polynomially faster than APSP" on arXiv:1011.6181.
A: In general it does not seem that the diameter computation implies APSP.
Indeed If the graph is undirected the following can be applied.
Pilu Crescenzi, Roberto Grossi, Michel Habib, Leonardo Lanzi, Andrea Marino: On computing the diameter of real-world undirected graphs. TCS 2012.
and if the graph is directed the following can be applied.
Pierluigi Crescenzi, Roberto Grossi, Leonardo Lanzi, Andrea Marino: On Computing the Diameter of Real-World Directed (Weighted) Graphs. SEA 2012.
In the worst case the complexity of these methods is the same as computing APSP, but in real world cases it has been experimentally shown that they run in O(m), where m is the number of edges. Both can be used even if the graph is weighted.
Regards
Andrea Marino
A: For road networks:
http://arxiv.org/abs/1209.4761
A: There is a rather nice algorithm by Johnson, with time $O(n^2 log n + mn)$; the reference is D. Johnson, Efficient algorithms for shortest paths in sparse graphs, Journal of the ACM, 24:1--13, 1977.
A: It is a longstanding open problem whether it is possible to compute the shortest path between a particular pair of vertices in time less than known algorithms for computing all-pairs shortest path. So you are asking whether there is an algorithm for computing the maximum over the set of all shortest paths that runs faster than any known algorithm for computing any particular shortest path.
I'm pretty sure the answer is no, but I can't off the top of my head think of a reduction to the single pair shortest path problem.
A: *

*
Extract MST.  

*
Find its diameter.  

*
Or am I wrong? :)  

