igraph高效提取多路径方法及双循环代码缺漏问题咨询

你调用all_simple_paths()获取到起点到终点的所有路径列表后，强制用[[1]]只取了列表的第一个元素，当两点之间存在多条路径时，除第一条之外的所有路径都会被丢弃，这就是你丢失B1 -> B2b -> B3的核心原因。

你可以直接遍历所有起点-终点对，把每次返回的路径列表直接合并到结果中，不需要提前固定结果容器长度，也不需要手动维护计数变量：

library(dplyr)
library(igraph)

d <- tribble(~input, ~output,
             "A1", "A2",
             "A2", "A3a",
             "A2", "A3b",
             "B1", "B2a",
             "B1", "B2b",
             "B2a", "B3",
             "B2b", "B3")
g <- graph_from_data_frame(d, directed = TRUE)
# 获取所有起点、终点
starts <- V(g)[degree(g, mode = "in") == 0]
finals <- V(g)[degree(g, mode = "out") == 0]
# 生成所有起点终点组合
path_pairs <- expand.grid(start = starts, end = finals, stringsAsFactors = FALSE)
# 遍历所有组合提取路径
res_collect <- unlist(apply(path_pairs, 1, function(pair) {
  all_simple_paths(g, from = pair[["start"]], to = pair[["end"]])
}), recursive = FALSE)
# 过滤空值后查看结果
res_collect <- Filter(Negate(is.null), res_collect)

运行后查看结果可以看到所有路径都被正确提取：

res_collect
# [[1]]
# + 3/8 vertices, named, from 2169594:
# [1] A1  A2  A3a
# 
# [[2]]
# + 3/8 vertices, named, from 2169594:
# [1] A1  A2  A3b
# 
# [[3]]
# + 3/8 vertices, named, from 2169594:
# [1] B1  B2a B3 
# 
# [[4]]
# + 3/8 vertices, named, from 2169594:
# [1] B1  B2b B3

• 如果你的图规模非常大，不需要遍历所有起点终点对，可提前筛选出存在可达性的对：先用distances()计算起点到终点的最短距离，过滤掉距离为无穷大的不可达对，再针对可达对调用all_simple_paths()，减少无效计算
• 不需要嵌套循环，用向量化的apply/purrr系列函数处理即可，代码更简洁，也避免手动维护计数的出错风险
• 如果只需要固定长度的路径，可给all_simple_paths()指定cutoff参数，提前终止过长路径的检索，大幅提升运行效率

内容的提问来源于stack exchange，提问作者r.user.05apr