Good algorithm for finding the diameter of a (sparse) graph?

algorithm math graph-theory
A. Rex picture A. Rex · Jul 27, 2009 · Viewed 15.2k times · Source

I have a large, connected, sparse graph in adjacency-list form. I would like to find two vertices that are as far apart as possible, that is, the diameter of the graph and two vertices achieving it.

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 shortest directed path from one vertex to another).

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

Edit: By "as far apart as possible", I of course mean the "longest shortest path" -- that is, the maximum over all pairs of vertices of the shortest distance from one to the other.

Answer

agorenst picture agorenst · Jul 28, 2009

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

Related questions

Calculate distance between two latitude-longitude points? (Haversine formula)

How do I calculate the distance between two points specified by latitude and longitude? For clarification, I'd like the distance in kilometers; the points use the WGS84 system and I'd like to understand the relative accuracies of the approaches available.

Read More
Unfamiliar symbol in algorithm: what does ∀ mean?

I'm reading about an algorithm (it's a path-finding algorithm based on A*), and it contains a mathematical symbol I'm unfamiliar with: ∀ Here is the context: v(s) ≥ g(s) = mins'∈pred(s)(v(s') + c(s', s)) ∀s ≠ sstart Can …

Read More
How do I calculate a point on a circle’s circumference?

How can the following function be implemented in various languages? Calculate the (x,y) point on the circumference of a circle, given input values of: Radius Angle Origin (optional parameter, if supported by the language)

Read More