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.