2
$\begingroup$

Is there any efficient algorithm to find shortest distance between all pairs of vertices?

The graph is:

  • Cyclic
  • Sparse (each vertex has either 2 or 3 edge)
  • undirected(bidirectional)
  • weighted
  • non-negative

Since Floyd-Warshall algorithm and Johnson's algorithm are best for finding shortest path for every pairs but:

  • Johnson's algorithm works on directed
  • Floyd-Warshall algorithm is best for dense graphs

I couldn't find any algo that is efficient for above graph conditions.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ If algorithm works on directed, it works on undirected as well (each non-directed edge can be converted to a pair of directed). $\endgroup$
    – rus9384
    Oct 14, 2017 at 15:14
  • $\begingroup$ @rus9384 "non-directed edge can be converted to a pair of directed" --how? $\endgroup$
    – wrangler
    Oct 14, 2017 at 15:33
  • 1
    $\begingroup$ If you have nondirected edge A---B, just replace it with A-->B and A<--B. $\endgroup$
    – rus9384
    Oct 14, 2017 at 16:29

1 Answer 1

Reset to default
3
$\begingroup$

Mikkel Thorup's paper Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time shows an $O(m)$ time algorithm for single-source shortest paths on undirected weighted graphs. That immediately implies an $O(mn)$ time algorithm for all pair shortest paths, which is the optimal $O(n^2)$ in your scenario.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The article seems to be paid and costly. Isn't any free link present? $\endgroup$
    – wrangler
    Oct 14, 2017 at 15:49
  • $\begingroup$ @wrangler I edited it. Now it should be a free link. $\endgroup$
    – Wei Zhan
    Oct 14, 2017 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.