如何在R的igraph包中查询带路径长度约束的最小代价最短路径？

Great question! The built-in shortest_paths() function in igraph prioritizes minimizing total edge weight above all else—so in your example, it returns the 3-edge path because it has the lowest overall cost, even though you want to limit paths to 2 edges max. Since igraph doesn't have a direct parameter for this edge-count constraint, here are two practical solutions:

Method 1: Enumerate All Valid Paths (Best for Small Graphs) #

If your graph isn't too large, you can generate all simple paths from your start to end node that meet the length constraint, then calculate their total weights and pick the smallest.

Step-by-Step Code #

library(igraph)

# Example graph matching your scenario
g <- graph_from_edgelist(matrix(c(2,1, 1,3, 3,7, 1,7), ncol=2, byrow=TRUE))
# Assign weights (adjust these to match your actual graph)
E(g)$weight <- c(1, 1, 1, 3) 

# Define parameters
start_node <- 2
end_node <- 7
max_edge_count <- 2 # Your desired maximum path length (number of edges)

# 1. Get all paths with ≤ max_edge_count edges
valid_paths <- all_simple_paths(g, from = start_node, to = end_node, cutoff = max_edge_count)

# 2. Calculate total weight for each path
path_weights <- sapply(valid_paths, function(path) {
  edges_in_path <- E(g, path = path)
  sum(edges_in_path$weight)
})

# 3. Find the path(s) with the minimum weight
min_weight <- min(path_weights)
best_paths <- valid_paths[path_weights == min_weight]

# Print results
cat("Minimum-cost paths with ≤", max_edge_count, "edges:\n")
for (path in best_paths) {
  cat(paste(names(path), collapse = " -> "), "| Total Weight:", min_weight, "\n")
}

How It Works #

• all_simple_paths() uses cutoff to limit paths to your maximum edge count (note: cutoff refers to number of edges, not vertices).
• We loop through each valid path, sum its edge weights, and filter for the smallest total weight.

Method 2: Matrix Power Approach (Best for Larger Graphs) #

For bigger graphs where enumerating all paths is computationally expensive, use a dynamic programming-style matrix method to compute minimum weights for paths of length 1 to l, then retrieve the corresponding path.

Step-by-Step Code #

library(igraph)

# Reuse the example graph from Method 1
g <- graph_from_edgelist(matrix(c(2,1, 1,3, 3,7, 1,7), ncol=2, byrow=TRUE))
E(g)$weight <- c(1, 1, 1, 3) 

start_node <- 2
end_node <- 7
max_edge_count <- 2

# 1. Initialize weighted adjacency matrix
adj_mat <- as_adjacency_matrix(g, attr = "weight", sparse = FALSE)
adj_mat[adj_mat == 0] <- Inf # Set non-edges to infinity
diag(adj_mat) <- 0 # Self-loop weight is 0

# 2. Compute minimum weights for paths of length 1 to max_edge_count
min_weights <- matrix(Inf, nrow = nrow(adj_mat), ncol = ncol(adj_mat))
diag(min_weights) <- 0 # Length 0 paths (self)

current_mat <- adj_mat
min_weights <- pmin(min_weights, current_mat) # Add length 1 paths

for (k in 2:max_edge_count) {
  # Compute min weight for k-edge paths using min-sum matrix multiplication
  current_mat <- matrix(
    apply(current_mat, 1, function(row) apply(adj_mat, 2, function(col) min(row + col))),
    nrow = nrow(adj_mat)
  )
  min_weights <- pmin(min_weights, current_mat)
}

# 3. Get the minimum weight, then find corresponding paths
target_min_weight <- min_weights[start_node, end_node]
valid_paths <- all_simple_paths(g, from = start_node, to = end_node, cutoff = max_edge_count)
best_paths <- valid_paths[sapply(valid_paths, function(p) sum(E(g, path=p)$weight)) == target_min_weight]

# Print results
cat("Minimum weight for ≤", max_edge_count, "edges:", target_min_weight, "\n")
cat("Best path(s):\n")
for (path in best_paths) {
  cat(paste(names(path), collapse = " -> "), "\n")
}

How It Works #

• We use matrix operations to iteratively compute the minimum weight for paths with exactly 1, 2, ..., max_edge_count edges.
• After finding the minimum weight for valid paths, we use all_simple_paths() to retrieve the actual path(s) (since matrix methods only give weights, not path sequences).

Key Notes #

• If you need paths with exactly l edges instead of ≤l, adjust the code to only consider the k=l iteration in Method 2, or filter valid_paths to those with length exactly l (check length(path)-1 == l).
• all_simple_paths() avoids cycles, so you don't have to worry about infinite loops.

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