0

我正在努力寻找一种有效的算法，它将为我提供有向图中 2 个节点之间的所有可能路径。

我找到了RGL gem，迄今为止计算速度最快。我能够使用Dijkstras Shortest Path Algorithm来自 gem 的最短路径。

尽管获得了许多解决方案（红宝石/非红宝石），但我用谷歌搜索，要么无法转换代码，要么代码需要永远计算（效率低下）。

我在这里主要是如果有人可以建议使用/调整RGLgem 本身的各种算法（如果可能的话）或其他一些有效的方式来查找所有路径。

有向图的输入可以是数组数组。

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

PS：只是为了避免负面投票/评论，不幸的是，我没有显示效率低下的代码片段，因为我几天前将其丢弃并且没有将其保存在任何地方以供记录或在此处复制。

4

1 回答 1

0

主要问题是两个节点之间的路径数量在整体节点数量中呈指数增长。因此，任何查找两个节点之间所有路径的算法在较大的图上都会非常慢。

例子：

作为一个例子，想象一个由 nxn 个节点组成的网格，每个节点都连接到它们的 4 个邻居。现在您要查找从左下角节点到右上角节点的所有路径。即使您只允许向右移动 (r) 和向上移动 (u)，您得到的路径也可以用任何长度为 2n 且 (r) 和 (u) 数量相等的字符串来描述。这将为您提供“2n 选择 n”条可能的路径（忽略其他移动和循环）

于 2018-01-02T11:52:10.543 回答