如何在igraph中查找两顶点间的最长路径？（附R代码示例）

你的示例是树结构（无环图），这种情况下可以通过反转边权重的方式，复用最短路径算法来计算最长路径——因为求权重和最大的路径，等价于求权重取反后权重和最小的路径。

修改后的代码实现 #

基于你提供的代码，调整如下：

# 加载包并创建示例图
library(igraph)
set.seed(123) # 设置随机种子保证结果可复现
g <- graph.tree(n = 10, children = 2)
E(g)$weight <- sample(1:10, length(E(g)), replace = TRUE)

# --------------------------
# 查找最长路径（权重和最大）
# --------------------------
# 反转边权重
E(g)$neg_weight <- -E(g)$weight

# 用反转后的权重计算最短路径，对应原权重的最长路径
longest_path_result <- shortest_paths(g, from = 1, to = 10, weights = E(g)$neg_weight, output = "both")
longest_path_edges <- longest_path_result$epath[[1]]
longest_cost <- sum(get.edge.attribute(g, "weight", index = longest_path_edges))

# 输出结果
cat(paste("Longest path (edge sequence):", paste(longest_path_edges, collapse = " -> "), "\n"))
cat(paste("Total weight of longest path:", longest_cost, "\n"))

# 对比原最短路径结果
shortest_path <- shortest_paths(g, from = 1, to = 10, output = "both")$epath[[1]]
shortest_cost <- sum(get.edge.attribute(g, "weight", index = shortest_path))
cat("\n--- 对比最短路径 ---\n")
cat(paste("Shortest path (edge sequence):", paste(shortest_path, collapse = " -> "), "\n"))
cat(paste("Total weight of shortest path:", shortest_cost, "\n"))

关键说明 #

• 树结构中任意两个顶点之间拓扑路径唯一，但因为边有权重，所以存在权重和的最大/最小区别，上述方法正好适配这种场景。
• 如果是带环的图：若存在正权重环，最长路径会无限长（可以绕环无限次累加权重），此时这种方法不适用；若所有环都是负权重环，仍然可以用取反权重的方式计算最长路径。

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