# Shortest path between all pairs of vertices in cyclic undirected weighted sparse graph

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.

• If algorithm works on directed, it works on undirected as well (each non-directed edge can be converted to a pair of directed). – rus9384 Oct 14 '17 at 15:14
• @rus9384 "non-directed edge can be converted to a pair of directed" --how? – wrangler Oct 14 '17 at 15:33
• If you have nondirected edge A---B, just replace it with A-->B and A<--B. – 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.