CODEWITHSUNDEEP
ruby-on-railsrubyalgorithmgraphruby-rgl
Md. Farhan Memon
Md. Farhan Memon

Reputation: 6121

Efficiently Finding all paths between 2 nodes in a directed graph - RGL Gem

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.

Upvotes: 0

Views: 671

Answers (1)

SaiBot
SaiBot

Reputation: 3745

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)

Upvotes: 0

Related Questions