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

**277** 观看

**1**回复

**5334**
作者的声誉

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 的来源 发布者: 2017 年 12 月 26 日### 回应 (1)

**0**像

**2328**
作者的声誉

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 发布者: 02.01.2018 11:52###### 来自类别的问题 :

- ruby-on-rails 如何在Ruby on Rails中“漂亮”格式化我的JSON输出？
- ruby-on-rails 在Rails应用程序上更新服务器端进度
- ruby-on-rails CouchDB文档模型更改？
- ruby-on-rails JRuby on Rails与Ruby on Rails有什么区别？
- ruby 为什么Ruby没有真正的StringBuffer或StringIO？
- ruby 如何在ruby中生成随机的10位数字？
- ruby 在Ruby中将数组转换为散列的最佳方法是什么？
- ruby 确定Ruby中的文件类型
- algorithm Function for creating color wheels
- algorithm 大O，你如何计算/近似它？
- algorithm 测量信号的峰值检测
- algorithm 拼图：找到最大的矩形（最大矩形问题）
- graph 在图形中生成明显不同的RGB颜色
- graph 为图形的Y轴选择有吸引力的线性刻度
- graph 你如何改变用matplotlib绘制的数字的大小？
- graph 图上“漂亮”网格线间隔的算法
- ruby-rgl Efficiently Finding all paths between 2 nodes in a directed graph - RGL Gem