R中长度为l的最短路径

Question

我想在由顶点和边组成的加权图中找到长度为 l 或更小且成本最低的最短路径。

  shortest_paths(g,from,to,output="both",weights=wts)

在 R 中（来自 igraph 包）给出了从顶点到顶点之间成本最低的最短路径，对长度 l 没有限制。

例如，在此图中，2 和 7 之间的最短路径是长度为 3 的 2 1 3 7，但我想要长度为 2 的最短路径，即最小成本的 2 1 7。

有人可以指导我如何进行。

Answer 1

在您的示例中，从 2 到 7 只有一条长度为 2 的路径。这使得我们很难测试我们是否真的获得了最小成本路径。所以，我添加了一个 link 来创建一个长度为 2 的额外路径。

## Extended example
to     = c(1,1,1,1,1,1,2,2,3,3,6)
from   = c(2,3,4,5,6,7,4,6,5,7,7)
weight = c(19,39,40,38,67,68,14,98,38,12,10)
EDF = data.frame(to, from, weight)
G   = graph_from_data_frame(EDF, directed = FALSE)
LO = layout_as_star(G, center=1, order = c(1,4,2,5,6,3,7))
plot(G, layout=LO, edge.label=E(G)$weight)

想法是从 all 路径从 2 到 7 和 select 只有那些满足约束的路径开始 - 路径长度 <= 2（注意这意味着顶点数 <=3)。对于这些路径，我们计算权重和 select 具有最小成本的路径。

maxlength = 2       ## maximum number of links
ASP = all_simple_paths(G, "2", "7")
ShortPaths = which(sapply(ASP, length) <= maxlength+1)
ASP[ShortPaths]
[[1]]
+ 3/7 vertices, named, from af35df8:
[1] 2 1 7
[[2]]
+ 3/7 vertices, named, from af35df8:
[1] 2 6 7

如您所见，有两条长度为二的路径。我们需要找到成本最低的那个。为了使这变得简单，我们创建了一个函数来计算路径的权重。

PathWeight = function(VP) {
    EP = rep(VP, each=2)[-1]
    EP = EP[-length(EP)]
    sum(E(G)$weight[get.edge.ids(G, EP)])
}

现在很容易得到所有的路径权重。

sapply(ASP[ShortPaths], PathWeight)
[1]  87 108

并选择最小的那个

SP = which.min(sapply(ASP[ShortPaths], PathWeight))
ASP[ShortPaths[SP]]
[[1]]
+ 3/7 vertices, named, from af35df8:
[1] 2 1 7

R中长度为l的最短路径

Shortest path of length l in R

r

graph

shortest-path

igraph