最短路径算法的替代项

Question

我有一个由335个节点组成的网络。我计算了所有节点之间的weighted shortest.paths。现在，我想看看在节点之间使用了哪些路径序列。

我在igraph中使用shortest_path命令，并遍历网络中所有节点组合（335²组合-335（从/到同一节点的路径为0）/ 2（图形是无向的）。因此，所有I必须迭代超过55.945个组合。

我的方法如下：net是我的网络sp_data是具有网络中所有链接组合的df

results1 <- sapply(sp_data[,1], function(x){shortest_paths(net, from = x, to = V(net), output="epath"})
不幸的是，这需要花一些时间来计算，最后我没有足够的内存来存储信息。 （Error: cannot allocate vector of size 72 Kb）。基本上我有两个问题：

1. shortest.paths命令如何需要几秒钟来计算网络中所有节点之间的距离，而提取路径序列（不仅仅是长度）需要几天并且超过了内存容量？

2. 是否有替代方法可获得所需的输出（最短路径的路径序列）？我猜想sapply语法应该已经比for::loop更快了？

我有一个由335个节点组成的网络。我计算了所有节点之间的加权shortest.paths。现在，我想看看在节点之间使用了哪些路径序列。我用...

Answer 1

您可以尝试cppRouting软件包。它提供get_multi_paths函数，该函数返回包含每个最短路径的节点序列的列表。