shortest_path算法的替代方案

Question

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

我在iGraph中使用shortest_path命令，并在我的网络中遍历所有节点组合(335 2组合-335(从/到同一节点的路径为0)/2 (无向图)。总之，我必须迭代超过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快了

Answer 1

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

library(igraph)
library(cppRouting)

#random graph
g <- make_full_graph(335) 

#convert to three columns data.frame 
df<-data.frame(igraph::as_data_frame(g),dist=1) 

#instantiate cppRouting graph
gr<-cppRouting::makegraph(df) 

#extract all nodes 
all_nodes<-unique(c(df$from,df$to))

#Get all paths sequence
all_paths<-get_multi_paths(Graph=gr,from=all_nodes,to=all_nodes)

#Get path from node 1 to 3
all_paths[["1"]][["3"]]