I am struggling to find 1 efficient algorithm which will give me all possible paths between 2 nodes in a directed graph.
我正在努力寻找一种有效的算法,它将为我提供有向图中2个节点之间的所有可能路径。
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.
我发现RGL宝石,到目前为止在计算方面最快。我能够使用来自gem的Dijkstras最短路径算法找到最短路径。
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.
我主要是在这里,如果有人可以建议使用/调整RGL gem本身的各种算法(如果可能的话)或其他一些有效的方法来查找所有路径。
Input of directed graph can be an array of arrays..
有向图的输入可以是数组的数组。
[[1,2], [2,3], ..]
[[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.
附: :只是为了避免负面投票/评论,遗憾的是我没有低效的代码片段,因为我在几天前丢弃它并且没有将它保存在任何地方以备记录或在此重现。
1 个解决方案
#1
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)
举例来说,想象一个n×n个节点的网格,每个节点连接到它们的4个邻居。现在,您要查找从左下方节点到右上方节点的所有路径。即使你只允许向右移动(r)并向上移动(u),你的结果路径也可以用任何长度为2n且字符数相等(r)和(u)的字符串来描述。这将为您提供“2n选择n”个可能的路径(忽略其他移动和循环)
#1
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)
举例来说,想象一个n×n个节点的网格,每个节点连接到它们的4个邻居。现在,您要查找从左下方节点到右上方节点的所有路径。即使你只允许向右移动(r)并向上移动(u),你的结果路径也可以用任何长度为2n且字符数相等(r)和(u)的字符串来描述。这将为您提供“2n选择n”个可能的路径(忽略其他移动和循环)