Optimizing search of all the shortest paths in a Graph with N vertices and N edges

1
votes

I need to find the shortest paths between all pairs in a Graph G. I'm using the Floyd–Warshall algorithm to compute the solution.

I need to know if there is a better option to find all the shortest paths given these facts about G:

  1. G is an undirected graph.
  2. The numbers of vertices and the edges is the same.
  3. All edge weights are positive.

Is there a better solution than Floyd–Warshall given these facts?

3
algorithmtreegraph-theoryshortest-path
The numbers of vertices and the edges is the same - Does it mean that graph is very sparse? – MBo
I don't know what that mean. (i don't have much background in graph theory) – eli.rodriguez
That is exactly what i mean – eli.rodriguez
I would say that #2 implies that the graph has one cycle, and 0 or more "tails". In that case, it should be fairly easy to beat Floyd-Warshall. – user3386109
Is the graph connected? – amit

3 Answers

4
votes

There is modification of Dijkstra Shortest Path algorithm for sparse graphs that works very fast and reveals log-linear (close to linear) asymptotic behavior. You need N searches from N vertices that gives O(N^2*LogN) asymptotic time that is better than O(N^3) Floyd–Warshall algorithm.

Probably your graph has special topology that allows more efficient approaches...

C++ code with Russian description (may be translated by Google Chrome)

I have delphi implementation for grid graph here.

1
votes

Have you tried Johnson's Algorithm? It seems to solve exactly your problem, i.e. APSP on a sparse weighted graph (with no circles of negative weight) https://en.wikipedia.org/wiki/Johnson%27s_algorithm

0
votes

Thanks @MBo @DubioserKerl , This is best approach that a found.

Since there are N vertices and N edges and the graph is connected , we know that there is only one cycle so , that cycle can be in a way "compressed" and save the "contentedness" of that cycle with the rest of the graph.

For example in the next graph the we can substitute the cycle c-d-e-g and create a new node h and save all externals the relation of the cycle 

a -> c
b -> d
f -> g

, so if we need find to paths between a and b we need

  1. Find the paths a - b in the collapsed graph using an LCA algoriths based to find the shortest path.

  2. And find the shortest paths between d - c in the cycle

enter image description here

I hope been clear enough the implementation is here