如何用R语言在无向图中计算各节点到指定节点的最短路径

问题描述 #

给定两个R数据框：

• edges_df：存储无向无权边，每行包含边ID、起点坐标(start_x, start_y)、终点坐标(end_x, end_y)
• nodes_df：存储节点信息，包含节点ID、节点坐标(x_value, y_value)

需要实现：计算每个节点到指定节点（如ID=3的节点）的最短路径。

原始数据定义 #

# 边数据框
edges_df <- data.frame(
  id=c(1,2,3,4,5,6,7,8,9,10), 
  start_x=c(46646.8,46646.8,46680.2,46680.2,46713.5,46713.5,46713.5,46662.2,46662.2,46662.2), 
  end_x=c(46646.8,46680.2,46780.5,45723.5,46813.5,46813.5,46962.2,47662.2,46662.2,44879.4), 
  start_y= c(7392.8, 7392.8,7459.4,7659.4,7659.4,7852.3, 7182.7, 7143.9, 7243.9, 7899.5), 
  end_y= c(7412.8, 7536.2,7346.2,7642.5, 7642.5, 7271.3,7653.7,7392.8,7921.4,7392.8)
)

# 节点数据框
nodes_df <- data.frame(
  id=c(1,2,3,4,5), 
  x_value= c(46728.9,46970.9,45236.9, 47852.9, 50123.9), 
  y_value= c(7463.89,7563.89,7417.89,7417.89,7407.89)
)

实现步骤 #

1. 匹配边的坐标到节点ID #

首先需要将边的起止坐标对应到nodes_df中的节点ID。由于是无向图，每条边需保留双向连接。若坐标存在精度误差，可使用round()统一小数位数后再匹配。

library(dplyr)

# 匹配起点坐标到节点ID
edges_df <- edges_df %>%
  left_join(nodes_df, by = c("start_x" = "x_value", "start_y" = "y_value")) %>%
  rename(from = id.y) %>%
  select(-id.x)

# 匹配终点坐标到节点ID
edges_df <- edges_df %>%
  left_join(nodes_df, by = c("end_x" = "x_value", "end_y" = "y_value")) %>%
  rename(to = id.y)

# 过滤无法匹配到节点的无效边
edges_clean <- edges_df %>% filter(!is.na(from) & !is.na(to))

2. 构建无向图对象 #

使用igraph包构建无向无权图：

library(igraph)

# 基于清洗后的边数据构建图，关联节点信息
graph <- graph_from_data_frame(edges_clean, directed = FALSE, vertices = nodes_df)

3. 计算最短路径 #

计算最短路径长度

获取所有节点到指定节点（如ID=3）的最短路径长度：

# 指定目标节点
target_node <- 3

# 计算所有节点到目标节点的最短路径长度
shortest_distances <- distances(graph, v = V(graph)[id == target_node], to = V(graph))

# 整理为可读的数据框
distance_result <- data.frame(
  node_id = V(graph)$id,
  distance_to_target = as.vector(shortest_distances)
)

print(distance_result)

获取具体路径节点

如果需要查看每个节点到目标节点的具体路径：

# 获取所有从目标节点出发的最短路径
paths <- all_shortest_paths(graph, from = V(graph)[id == target_node])

# 遍历输出每个节点的路径
for (node in V(graph)$id) {
  if (node == target_node) {
    cat("节点", node, "到目标节点的路径：[自身]\n")
  } else {
    # 筛选包含当前节点的路径
    node_paths <- paths$res[sapply(paths$res, function(p) node %in% p$id)]
    if (length(node_paths) > 0) {
      path_ids <- sapply(node_paths, function(p) p$id)
      cat("节点", node, "到目标节点的路径：", paste(path_ids[[1]], collapse = " -> "), "\n")
    } else {
      cat("节点", node, "到目标节点无连通路径\n")
    }
  }
}

注意事项 #

• 若原始数据中边与节点的坐标无法直接匹配，需检查数据精度或调整匹配逻辑（如统一小数位数）。
• 孤立节点的最短路径长度会显示为Inf，表示无连通路径。

内容的提问来源于stack exchange，提问作者The Curious One