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).