长度l在R中的最短路径

在您的示例中,只有一条长度为2到7的路径。这使得我们很难测试我们是否真的获得了最小成本路径。因此,我添加了一个链接来创建长度为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)

我们的想法是 全部的 从2到7的路径,并仅选择满足约束的路径-路径长度<=2(请注意,这表示顶点数lt;=3)。对于这些路径,我们计算权重并选择成本最小的路径。

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

如您所见,有两条路径的长度为2。我们需要找到一个成本最低的。为了简化此操作,我们创建了一个函数来计算路径的权重。

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