目前,我正在开展一个涉及纽约出租车数据的项目,在这个项目中,我可以获得一个人在网络中被接送的地方。
我正在使用ESRI
shapefile
,我可以用igraph
包加载到R作为shp2graph
对象;我需要利用Dijkstra算法(或类似的最短路径算法)来找到两个给定顶点之间的单个最短路径。我认为get.shortest.paths()
包的igraph
方法将是我的解决方案,但令我惊讶的是,它计算了从顶点到网络中所有其他路径的所有最短路径。
对我来说,这似乎有些过分,因为我只需要两个指定节点之间的一条路径。我在网上和igraph
文档中做了一些讨论,但我能找到的只是计算从给定顶点到所有其他顶点的许多最短路径的方法。
由于从顶点计算每一条最短路径的计算成本如何,然后只从列表的庞然大物中选择一条,我正在寻找一种方法在图中的两个指定顶点之间使用Dijkstra算法。有没有办法在igraph
包中做到这一点,或者如果没有,是否有一个很好的方法来使用R中的不同包来做到这一点?
编辑:最后,我希望找到一个函数,它将接收图形对象和两个顶点的ID,我希望找到它们之间的最短路径,然后返回一个路径/边缘(或ID)列表最短路径。这将帮助我沿着两个顶点之间的最短路径检查每条街道。
编辑:作为我目前如何使用该函数的一个例子:path <- get.shortest.paths(NYCgraph, from=32, mode="out")
。我希望找到的是path <- shortestPathFunction(NYCgraph, from=32, to=37)
任意计算顶点ID 32和顶点ID 37之间的最短路径(网络中的两个随机街道交叉点)。
我发现了我的问题,这是在我调用get.shortest.paths()之前发生的。对于那些对如何读取ESRI shapefile感兴趣的人,并找到两点之间的单一最短路径(这是我的困境):
myShapefile <- readOGR(dsn=".", layer="MyShapefileName") # i.e. "MyShapefileName.shp"
shpData <- readshpnw(myShapefile, ELComputed=TRUE)
igraphShpObject <- nel2igraph(shpData[[2]], shpData[[3]], weight=shpData[[4]])
testPath <- get.shortest.paths(igraphShpObject, from=42, to=52) # arbitrary nodes
testPath[1] # print the node IDs to the console
此外,如果有人想要获取连接两个节点(可能来自testPath中的节点)的边的ID:
get.edge.ids(igraphShpObject, c(42,45) # arbitrary nodes 42 and 45
此索引与shpData中的索引相同;例如,如果要获取边缘ID x的长度(如get.edge.ids()
中所示),则可以键入shpData[[4]][x]
。
我希望这些花絮可能对将来遇到同样问题的人有所帮助!这种方法利用R中的shp2graph
,rgdal
和igraph
包。