0

I am struggling to find 1 efficient algorithm which will give me all possible paths between 2 nodes in a directed graph.

I found RGL gem, fastest so far in terms of calculations. I am able to find the shortest path using the Dijkstras Shortest Path Algorithm from the gem.

I googled, inspite of getting many solutions (ruby/non-ruby), either couldn't convert the code or the code is taking forever to calculate (inefficient).

I am here primarily if someone can suggest to find all paths using/tweaking various algorithms from RGL gem itself (if possible) or some other efficient way.

Input of directed graph can be an array of arrays..

[[1,2], [2,3], ..]

P.S. : Just to avoid negative votes/comments, unfortunately I don't have inefficient code snippet to show as I discarded it days ago and didn't save it anywhere for the record or reproduce here.

Md. Farhan Memon
  • 6,055
  • 2
  • 11
  • 36
  • "I am able to find the shortest path using the Dijkstras Shortest Path Algorithm from the gem" - So, i would suggest look into the gem `rgl` implementation. May be they calculate all possible paths before finding the shortest path. May be. I don't have much idea about Dijkstra's. – Jagdeep Singh Dec 26 '17 at 13:34
  • Dijkstra's algorithm is for specifically finding the shortest path. It does not calculate all paths. I don't know if there are any shortcuts to finding all paths...that sounds like a necessarily slow operation on large graphs. Related: https://stackoverflow.com/a/9535898/2473275 – Jami Couch Dec 26 '17 at 16:51
  • @JagdeepSingh nope, as mentioned by Jami Couch, it doesn't calculate all paths. – Md. Farhan Memon Dec 27 '17 at 12:00
  • Thanks @JamiCouch for the related post, it seems to be a np hard problem. I am still being optimistic that there should be 1 hack/work around method where it can be achieved. I don't know, maybe, calling dijkstra's with variation in weights may result in different path..maybe..just thinking on those lines now.. – Md. Farhan Memon Dec 27 '17 at 12:03

1 Answers1

0

The main problem is that the number of paths between two nodes grows exponentially in the number of overall nodes. Thus any algorithm finding all paths between two nodes, will be very slow on larger graphs.

Example:

As an example imagine a grid of n x n nodes each connected to their 4 neighbors. Now you want to find all paths from the bottom left node to the top right node. Even when you only allow for moves to the right (r) and moves up (u) your resulting paths can be described by any string of length 2n with equal number of (r)'s and (u)'s. This will give you "2n choose n" number of possible paths (ignoring other moves and cycles)

SaiBot
  • 3,595
  • 1
  • 13
  • 19