15
$\begingroup$

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

Improve this question
$\endgroup$
4
  • $\begingroup$ See the "non-matrix methods" section of sawww.epfl.ch/SIC/SA/publications/SCR98/scr10-page3.html $\endgroup$
    – Steve Huntsman
    Commented Jan 11, 2010 at 16:49
  • 1
    $\begingroup$ @Steve: Thanks for the reference. Their "matrix methods" section essentially runs 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
    Commented Jan 11, 2010 at 17:17
  • 1
    $\begingroup$ Do you need the exact diameter, or would approximate methods suffice? (I have the suspicion that an exact "truly subcubic" diameter finding algorithm would yield a subcubic all-pairs shortest paths algorithm on unweighted graphs. But note, the latter can be theoretically solved in matrix multiplication time...) $\endgroup$
    – Ryan Williams
    Commented Jan 13, 2010 at 1:45
  • 1
    $\begingroup$ I just wonder. If the graph is a tree, then there is a simple trick. Just, start with a point, find the point furthest away. Then search the point furthest away from that point. Then you have the longest path (or one of them, in case of multiple solutions). Suppose you apply the same method on a graph, instead of tree. The points on the paths already found, can not be the end points of such longest path. So, you skip them as potential candidates. You repeat this, until all points have been tried. Could this work? $\endgroup$
    – Lucas K.
    Commented Dec 6, 2010 at 21:04

6 Answers 6

Reset to default
9
$\begingroup$

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.

Improve this answer
$\endgroup$
5
$\begingroup$

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

Improve this answer
$\endgroup$
2
$\begingroup$

For road networks: http://arxiv.org/abs/1209.4761

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I asked if there was a better approach than computing all-pairs shortest paths. Johnson's algorithm computes all-pairs shortest paths by running Dijkstra for each vertex (after a preprocessing step take makes weights non-negative). $\endgroup$
    – aorq
    Commented Jan 11, 2010 at 17:11
  • 1
    $\begingroup$ Well, I more or less doubt one can compute the diameter without doing work equivalent to computing all shortests paths... $\endgroup$
    – Mariano Suárez-Álvarez
    Commented Jan 12, 2010 at 0:58
1
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ What? Computing the shortest path between a pair of vertices takes at most as long as the single-source shortest path problem, which can be solved by Dijkstra's algorithm in time O(V log V + E). The best known all-pairs shortest path algorithm is Johnson's algorithm (running Dijkstra for each vertex), which takes time O(V^2 log V + VE). What's this "longstanding open problem"? $\endgroup$
    – aorq
    Commented Jan 12, 2010 at 15:43
  • $\begingroup$ Djikstra's algorithm does not work for negative edge weights; for this, you need Bellman Ford, which runs in time O(|V||E|) = O(|V|^3) for dense graphs. The best algorithm for the all-pairs shortest paths is Floyd-Warshall, which also runs in time O(|V|^3). Note that Johnson's algorithm is faster only on sparse graphs. $\endgroup$
    – Wilson
    Commented Jan 12, 2010 at 17:31
  • $\begingroup$ I see, thanks for the details. However, my question above is for unweighted, sparse graphs. At worst, I can restrict to sparse graphs with positive weights. $\endgroup$
    – aorq
    Commented Jan 12, 2010 at 20:47
-2
$\begingroup$
  1. Extract MST.
  2. Find its diameter.
  3. Or am I wrong? :)
Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ The diameter of the MST can be larger than the diameter of the underlying graph. For instance even if the underlying graph is something as simple as an unweighted complete graph, its diameter is one but any tree has diameter at least two. $\endgroup$
    – David Eppstein
    Commented Apr 17, 2011 at 17:59
  • $\begingroup$ @David; The nice counterexample of yours. PS I was too sleepy at the time of my answering. Have a nice day, everybody! $\endgroup$
    – trg787
    Commented Apr 18, 2011 at 3:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .