首页 文章

R：计算两个顶点之间的单个最短路径

提问于
浏览 次
0

目前，我正在开展一个涉及纽约出租车数据的项目，在这个项目中，我可以获得一个人在网络中被接送的地方 .

我正在使用 ESRI shapefile ，我可以使用 shp2graph 包将其作为 igraph 对象加载到R中;我需要利用Dijkstra算法（或类似的最短路径算法）来找到两个给定顶点之间的单个最短路径 . 我认为 igraph 包的 get.shortest.paths() 方法将是我的解决方案，但令我惊讶的是，它计算了从顶点到网络中所有其他路径的所有最短路径 .

对我来说，这似乎有些过分，因为我只需要两个指定节点之间的一条路径 . 我在网上和 igraph 文档中做了一些讨论，但我能找到的只是计算从给定顶点到所有其他顶点的许多最短路径的方法 .

由于从顶点计算每一条最短路径，然后只是从列表的庞然大物中选择一条，计算成本如何昂贵，我在图中的两个指定顶点之间进行算法 . 有没有办法在 igraph 包中执行此操作，或者如果没有，是否有一个很好的方法在R中使用不同的包执行此操作？

EDIT: 最后，我希望找到一个函数，它将接收图形对象和两个顶点的ID，我希望找到它们之间的最短路径，然后返回沿着最短路径的路径/边缘（或ID）列表路径 . 这将帮助我沿着两个顶点之间的最短路径检查每条街道 .

EDIT: 作为我目前如何使用该功能的示例： path <- get.shortest.paths(NYCgraph, from=32, mode="out") . 我希望找到的东西是 path <- shortestPathFunction(NYCgraph, from=32, to=37) 来任意计算顶点ID 32和顶点ID 37之间的最短路径（网络中的两个随机街道交叉点） .

r algorithm spatial shortest-path dijkstra

1 回答

  • 2

    我发现了我的问题，这是在我调用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 包 .

    回复于

相关问题