如何在igraph中统计最短路径上的顶点数量？

我完全理解你的需求——在铁路网络场景里，你需要从最短路径中提取车站总数（对应路径顶点数），进而算出换乘次数（中间车站数），但shortest.paths()只返回了路径权重和的矩阵，确实满足不了这个需求。

下面是具体的解决步骤和代码，基于igraph库来实现：

核心思路 #

shortest.paths()仅返回路径的权重总和，要获取路径的具体顶点序列，得用get.shortest.paths()（单条最短路径）或all_shortest_paths()（所有权重相同的最短路径）函数，再通过统计路径顶点序列的长度得到顶点数，最后推导换乘次数。

代码实现 #

1. 生成你的加权有向图（复用你的代码） #

library(igraph)
g <- erdos.renyi.game(25, 1/10, directed = TRUE)
E(g)$weight <- runif(length(E(g)), 1, 5)

2. 统计所有顶点对的最短路径顶点数 #

# 生成所有顶点对的组合
vertex_pairs <- expand.grid(from = V(g), to = V(g), stringsAsFactors = FALSE)

# 初始化存储顶点数的矩阵，维度和顶点数一致
path_vertex_count <- matrix(nrow = vcount(g), ncol = vcount(g))

# 遍历每个顶点对，计算最短路径的顶点数
for (i in 1:nrow(vertex_pairs)) {
  from_v <- vertex_pairs$from[i]
  to_v <- vertex_pairs$to[i]
  
  # 处理顶点到自身的情况：顶点数为1，无换乘
  if (from_v == to_v) {
    path_vertex_count[from_v, to_v] <- 1
    next
  }
  
  # 获取从from到to的最短路径顶点序列
  shortest_path <- get.shortest.paths(
    g, 
    from = from_v, 
    to = to_v, 
    mode = "out",  # 因为是有向图，指定方向为出边
    weights = E(g)$weight
  )$vpath[[1]]
  
  # 顶点数就是序列的长度
  path_vertex_count[from_v, to_v] <- length(shortest_path)
}

3. 计算换乘次数（中间顶点数） #

换乘次数等于总顶点数减去起点和终点，也就是顶点数 - 2，再单独处理顶点到自身的情况：

# 初始化换乘次数矩阵
transfer_count <- path_vertex_count - 2
# 自身到自身的换乘次数设为0
transfer_count[path_vertex_count == 1] <- 0

4. 处理多最短路径的情况（可选） #

如果存在多条权重总和相同的最短路径，get.shortest.paths()只返回第一条。如果你需要统计所有可能路径的顶点数，可以用all_shortest_paths()：

# 重新初始化矩阵用于存储多路径的顶点数（示例取第一条路径的顶点数，也可统计所有可能值）
multi_path_vertex_count <- matrix(nrow = vcount(g), ncol = vcount(g))

for (i in 1:nrow(vertex_pairs)) {
  from_v <- vertex_pairs$from[i]
  to_v <- vertex_pairs$to[i]
  
  if (from_v == to_v) {
    multi_path_vertex_count[from_v, to_v] <- 1
    next
  }
  
  # 获取所有最短路径的顶点序列
  all_paths <- all_shortest_paths(
    g, 
    from = from_v, 
    to = to_v, 
    mode = "out", 
    weights = E(g)$weight
  )$res
  
  # 这里示例取第一条路径的顶点数，你也可以统计所有路径的顶点数分布
  multi_path_vertex_count[from_v, to_v] <- length(all_paths[[1]])
}

结果说明 #

• path_vertex_count矩阵中，[i,j]的值表示从顶点i到顶点j的最短路径上的总车站数（比如你例子中的A-E-B-C对应值为4）。
• transfer_count矩阵中，[i,j]的值就是换乘次数（对应例子中的2次换乘）。

内容的提问来源于stack exchange，提问作者FilipeTeixeira