基于路由优先级的有向图顶点累积和计算（R/Python实现）

解决思路 #

要满足你的三个条件，核心是通过自定义边权重引导最短路径算法选择符合优先级的路径，同时保留所有原始边：

• 给Fiber类型边设置更低的基础权重，确保其优先级高于Micro；
• 同类型边的权重直接使用物理距离，保证距离更短的边被优先选择；
• 通过最短路径算法自动筛选符合条件的路径，无需增删任何边。

实现代码 #

library(igraph)
library(dplyr)

# 原始边数据
edges <- tribble(
  ~from,  ~to, ~tipo, ~distance_km, ~color, ~width,
  "A",    "B", "Fiber", 10, "black", 2,
  "B",    "C", "Fiber", 5, "black", 2,
  "B",    "C", "Fiber", 6, "gray", 0.5,
  "A",    "C", "Micro", 5, "gray", 0.5,
  "C",    "D", "Micro", 1, "black", 2,
  "C",    "D", "Micro", 2, "gray", 0.5
)

edges <- edges %>%
  mutate(label = paste0(tipo, " (", distance_km, ")"))

# 创建有向图
g <- graph_from_data_frame(edges, directed = TRUE)
V(g)$name <- paste0(V(g)$name, " (", 1:4, ")")

# 自定义边权重：Fiber用距离作为权重，Micro用1000+距离（确保Fiber优先级更高）
E(g)$weight <- ifelse(E(g)$tipo == "Fiber", 
                      E(g)$distance_km, 
                      1000 + E(g)$distance_km)

# 指定起点（对应原始顶点A）
start_vertex <- "A (1)"

# 计算从起点到所有顶点的最短路径（基于自定义权重）
path_list <- shortest_paths(g, v = start_vertex, mode = "out", weights = E(g)$weight)$vpath

# 计算顶点累积和：每个顶点的累积和为路径上的顶点数量（每个顶点权重为1）
cumulative_sum <- sapply(path_list, function(path) length(names(path)))
names(cumulative_sum) <- V(g)$name

# 输出结果
print(cumulative_sum)

结果说明 #

运行代码后会输出每个顶点的累积和：

A (1) B (2) C (3) D (4) 
    1     2     3     4 

这个结果完全符合你期望的黑色路径（A→B→C→D）的累积计算，同时所有原始边都被保留，没有增删操作。

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