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.

  • 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 '17 at 15:14
  • $\begingroup$ @rus9384 "non-directed edge can be converted to a pair of directed" --how? $\endgroup$ – wrangler Oct 14 '17 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 '17 at 16:29

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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