1

下面的例子给出了最短路径 1-2-6-7-3-4，其中只考虑了边的权重；并且不计算顶点处的转弯权重。有人可以建议一个程序来包括每个顶点的权重，即不转、右转或左转？我们可以假设 (NT, RT, LT)=(0,0.5,1) 的权重。当边缘权重与转弯效应相结合时，最短路径将变为 1-2-3-4。以下是有问题的示例。谢谢你。

# 
library(igraph)
n <- c(1,2,3,4,5,6,7,8)
x <- c(1,4,7,10,1,4,7,10)
y <- c(1,1,1,1,4,4,4,4)
node <- data.frame(n,x,y)
fm <- c(1,2,3,5,6,7,1,2,3,4)
to<-c(2,3,4,6,7,8,5,6,7,8)
weight<- c(1,4,1,1,1,2,5,1,1,1)
link <- data.frame(fm,to,weight)
g <- graph.data.frame(link,directed=FALSE,vertices=node)
sv <- get.shortest.paths(g,1,4,weights=NULL,output="vpath")
sv
E(g)$color <- "pink"
E(g, path=sv[[1]])$width <- 8
plot(g,edge.color="red") 
plot(g,edge.label=weight,edge.label.color="blue",edge.label.cex=2)
4

2 回答 2

0

原则上，Jeffery 是在描述我们想要什么，但问题的规模如此之大，以至于我们需要一个程序化的解决方案。可能有 200,000 个具有 3 到 6 条边的顶点。如果有办法爆炸，例如，4 边进和 4 边外的标准交点通过左移动到 16 右，并自动分配左通和右罚分。

最重要的是，与在传统的交叉口/顶点转弯相比，在 T 交叉口转弯（易于寻路）的惩罚更少

对于庞大的网络来说，这是否易于处理？

于 2013-11-14T20:14:28.367 回答
0

作为预处理步骤：对于v具有a传入边和b传出边的每个顶点，将其拆分为a连接到这些传入边的b顶点和连接到这些传出边的顶点。然后创建代表中间车削成本的边。

于 2013-11-14T06:38:18.077 回答