Well, I’ve put a little bit of thought on the problem, and a bit of googling, and I’m sorry, but I can’t find any algorithm that doesn’t seem to be “just find all pairs shortest path”.
However, if you assume that Floyd-Warshall is the only algorithm for computing such a thing (Big-Theta of |V|^3), then I have a bit of good news for you: Johnson’s Algorithm for Sparse Graphs (thank you, trusty CLRS!) computes all pairs shortest paths in (Big-Oh (|V|^2 * lgV + VE)), which should be asymptotically faster for sparse graphs.
Wikipedia says it works for directed (not sure about undirected, but at least I can’t think of a reason why not), here’s the link.
Is there anything else about the graph that may be useful? If it can be mapped easily onto a 2D plane (so, its planar and the edge weights obey the triangle inequality [it may need to satisfy a stricter requirement, I’m not sure]) you may be able to break out some geometric algorithms (convex-hull can run in nlogn, and finding the farthest pair of points is easy from there).
Hope this helps!
– Agor
Edit: I hope the link works now. If not, just google it. 🙂