5

I want to do a shortest path algorithm. My direct and not acyclic graph contains only positive numbers. I have to do the scan for all pairs of nodes in complete depth in python. My graph is big (100x100x100 (with time-steps) and I have to do it in a time efficient way. I tried to do it with Dijkstra but it was far too slow. I also tried a Floyd-Warshall algorithm but I think that this algorithm doesn't scan the graph in complete depth (?). I would be thankful for other algorithms and additional advices.

maxmitz
  • 659
  • 3
  • 11
  • Is your graph acyclic ? – Kuifje May 31 '21 at 08:41
  • No, it is not acyclic. – maxmitz May 31 '21 at 08:45
  • 2
    You can refer to this post for an answer. – Kuifje May 31 '21 at 08:50
  • 2
    Are you looking for the shortest path between two specific nodes? or between one specific node and all other nodes? or between all pairs of nodes? – fontanf May 31 '21 at 11:23
  • Between all pairs of nodes. – maxmitz May 31 '21 at 16:24
  • 1
    Then, the most efficient is to run a Dijkstra algorithm for each node. If you really want the shortest paths between all pairs, there is not much more you can do. Your options are: 1) not computing the shortest paths between all pairs, for example, for each node, you only compute the shortest paths to the 100 closest nodes, 2) use a better implementation, in Cython or C++, you might already gain a factor 10, but it might not be sufficient – fontanf Jun 01 '21 at 06:33
  • Thank you. I will try it! – maxmitz Jun 01 '21 at 07:35
  • It might be outdated, but for efficient C++ implementations of shortest path algorithms for road networks (ie. very sparse graphs) you can read this "old" post: http://stegua.github.io/blog/2012/09/19/dijkstra/ – Stefano Gualandi Jun 03 '21 at 06:43
  • 1
    If the graph is very dense (i.e. the number of edges is close to the number of vertices squared) Floyd-Warshall would be faster than Dijkstra. I don't understand what you mean by "scan the graph in complete depth"? – Paul Bouman Jun 03 '21 at 18:27
  • 2
    Also, could you give a bit more information about the structure of your graph? Do you have some information related to the time-steps, for instance? For example, if you can assume that the distance between two nodes can never be more than their distance in time, more clever algorithms than Dijkstra or Floyd-Warshall could be possible. – Paul Bouman Jun 03 '21 at 18:47

1 Answers1

1

I think these are promising options:

  1. floyd-warshall algorithm for dense graphs
  2. johnson algorithm for sparse graphs
  3. (not sure if it's worth to try and it will work well) dijkstra algorithm parallelized for each vertex

Regarding your question, a correct floyd-warshall implementation scans all the pairs.

user1403546
  • 111
  • 2