igraph自定义最短路径函数异常：节点1到165无结果求助

我用R语言的igraph库实现最短路径查找，节点1到14能正常运行，但查找节点1到165时函数无结果返回，图中包含165+个顶点，相关代码如下：

library(igraph)

graph <- list("1"=c("14"),
              "2"=c("3"),            
              "3"=c("2","9","15"),
              # 此处省略剩余节点定义
              )

weights <- list("1"=c(220),
                "2"=c(70),
                "3"=c(70,40,30),
                # 此处省略剩余权重定义
                )

G <- data.frame(stack(graph), weights = stack(weights)[[1]])

set.seed(500)
el <- as.matrix(stack(graph))
g <- graph_from_edgelist(el)

oldpar <- par(mar = c(1, 1, 1, 1))
plot(g, edge.label = stack(weights)[[1]], vertex.size = 5, edge.width 
= 2, edge.arrow.size = 0.2, edge.label.cex = 0.4, vertex.label.cex = 
0.6)
par(oldpar)

#####
path_length <- function(path) {
  if (is.null(path)) return(Inf)
  pairs <- cbind(values = path[-length(path)], ind = path[-1])
  sum(merge(pairs, G)[ , "weights"])
}

find_shortest_path <- function(graph, start, end, path = c()) {
  if (is.null(graph[[start]])) return(NULL)
  path <- c(path, start)
  if (start == end) return(path)
  
  shortest <- NULL
  
  for (node in graph[[start]]) {
    if (!(node %in% path)) {
      newpath <- find_shortest_path(graph, node, end, path)
      if (path_length(newpath) < path_length(shortest))
        shortest <- newpath
    }
  }
  
  shortest
}

find_shortest_path(graph, "1", "165")

问题原因 #

• 自定义递归函数效率极低：你实现的find_shortest_path是无剪枝的深度优先搜索（DFS），当节点数达到165+时，递归分支会指数级膨胀，导致程序长时间无响应，表现为“无法运行”。
• 未利用igraph原生优化函数：igraph内置了经过高度优化的最短路径算法（如Dijkstra、Bellman-Ford），处理大节点图的性能远胜于自定义递归实现。
• 潜在的图结构问题：若节点165未在graph列表中定义，或节点1与165属于不同连通分量，函数会直接返回NULL。

解决方案 #

1. 改用igraph原生函数（推荐） #

直接使用igraph内置函数，效率和可靠性都有保障：

library(igraph)

# 确保graph和weights列表完整定义所有节点及边权重
G <- data.frame(stack(graph), weights = stack(weights)[[1]])
# 构建带权重的图，根据实际情况设置directed（是否有向）
g <- graph_from_data_frame(G, directed = FALSE)

# 查找最短路径
shortest_path_result <- get.shortest.paths(g, from = "1", to = "165", weights = E(g)$weights)
# 获取路径长度
path_length_result <- shortest.paths(g, v = "1", to = "165", weights = E(g)$weights)

# 输出结果
cat("最短路径节点：", V(g)$name[shortest_path_result$vpath[[1]]], "\n")
cat("最短路径长度：", path_length_result, "\n")

2. 排查图的连通性 #

若原生函数也返回空结果，需验证：

• 节点165是否存在：print(V(g)$name)，确认"165"在列表中
• 节点1与165是否连通：comp <- components(g)，查看comp$membership["1"]和comp$membership["165"]是否相等，相等则连通，否则无路径

3. 优化自定义函数（不推荐） #

若必须使用自定义实现，需添加剪枝逻辑，避免无效递归：

# 带剪枝的改进版函数
find_shortest_path_pruned <- function(graph, start, end, path = c(), current_len = 0, shortest_len = Inf) {
  if (is.null(graph[[start]])) return(NULL)
  
  path <- c(path, start)
  
  if (start == end) return(list(path = path, length = current_len))
  
  shortest_path <- NULL
  
  for (node in graph[[start]]) {
    if (!(node %in% path)) {
      # 获取当前边的权重
      edge_idx <- which(graph[[start]] == node)
      edge_weight <- weights[[start]][edge_idx]
      new_len <- current_len + edge_weight
      
      # 剪枝：当前路径长度已超过已知最短，直接跳过
      if (new_len >= shortest_len) next
      
      sub_result <- find_shortest_path_pruned(graph, node, end, path, new_len, shortest_len)
      
      if (!is.null(sub_result)) {
        if (sub_result$length < shortest_len) {
          shortest_len <- sub_result$length
          shortest_path <- sub_result$path
        }
      }
    }
  }
  
  shortest_path
}

# 调用优化后的函数
result <- find_shortest_path_pruned(graph, "1", "165")
print(result)

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