R：计算两个顶点间的单个最短路径
目前，我正在从事一个涉及纽约市出租车数据的项目，在该项目中，我得到了一个人在网络中被接送的位置。
我正在使用ESRIshapefile，我可以用ShP2Graph包将其作为igraph对象加载到R中；我需要利用Dijkstra算法（或类似的最短路径算法）来找到两个给定顶点之间的单个最短路径。我认为igraph包的get.shortest.paths()方法是我的解决方案，但令我惊讶的是，它计算了从一个顶点到网络中所有其他顶点的所有最短路径。
对我来说，这似乎是矫枉过正，因为在两个指定节点之间只需要一条路径。我在网上和igraph文档中做了一些探索，但我能找到的只是围绕计算从给定顶点到所有其他顶点的许多最短路径的方法。
由于计算从一个顶点开始的每一条最短路径，然后从庞大的列表中选择一条路径，计算起来非常昂贵，所以我正在寻找一种方法，在图中的两个指定顶点之间利用Dijkstra算法。在igraph包中有没有一种方法可以做到这一点，或者如果没有，有没有一种好的方法可以在R中使用不同的包来做到这一点？
编辑：最后，我希望寻找一个函数，它将接受图形对象和两个顶点的ID，我希望找到之间的最短路径，然后返回沿着最短路径的路径/边（或ID）列表。这将有助于我沿着两个顶点之间的最短路径检查每条单独的街道。
Edit：作为我当前如何使用函数的示例:path<-get.shortest.paths（NYCgraph,from=32,mode=“out”）。我希望找到的东西是path<-shortestPathFunction(NYCgraph，FROM=32,to=37)，以任意计算顶点ID 32和顶点ID 37（网络中的两个随机街道交叉口）之间的最短路径。
共有1个答案
我发现了我的问题，它发生在调用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
此外，如果有兴趣获得连接两个节点的边缘的ID（可能来自testPath中的节点）：
get.edge.ids（igraphShpObject,c(42,45)#任意节点42和45
-
因此，如果我在一个图中有两个顶点，它们通过一个以上的边连接，而它们之间有相同的最短路径（即，如果我有节点a和节点B，它们直接通过三条边连接（它们之间有三条最短路径，每个距离为1)，所以计数应该返回3）我该如何修改BFS算法来实现这一点？这是我的代码，它只计算2个节点之间的最短路径，而不计算这些最短路径的个数。
-
下面的堆栈溢出问题 我尝试了在语句中使用两个重复的多个构造，但无法为每个起始顶点获得独立的。我也在使用平台，因此它限制了Gremlin的使用，其中不允许使用循环/脚本。所有gremlin查询必须以并由与链接在一起的命令组成 https://docs.aws.amazon.com/neptune/latest/userguide/access-graph-gremlin-differences.ht
-
我正在尝试编写一个算法，该算法将重建Floyd-Warshall算法中所有顶点对之间的最短路径（如果有，则为最短路径绑定多条路径）。我从这个问题中得到了一些提示：https://stackoverflow.com/a/11371588/7447425 基于此，我修改了Floyd Warshall算法： 该图是边缘列表的形式，例如： 到目前为止，一切似乎都很顺利。 对于路径重建， 但这不管用。那么，
-
王国连通性 对查尔斯国王来说，这是繁荣的一年，他正在迅速扩大他的王国。一个美丽的新王国最近已经建成，在这个王国里有许多城市由多条单向道路连接。两个城市可能由多条道路直接连接，这是为了确保高度连接。 在这个新王国中，查尔斯国王将其中一个城市作为他的金融首都，另一个作为战争首都，他希望这两个首都之间有高度的连通性。一对城市的连通性，比如城市A和城市B，被定义为从城市A到城市B的不同路径的数量。如果可能
-
以下是练习： null null 我的算法正确吗？如果我做v到w，然后做w到v，这仍然被认为是线性时间吗？
-
在无向赋权图中寻找两个顶点之间的最短路径。还已知权重是小于log（logV）的整数，其中V是顶点的数量。使用贝尔曼-福特或Dijkstra算法很容易解决，但是有没有什么算法可以更快地解决呢？ 到目前为止，我一直在考虑使用BFS，将权重大于1的边划分成两个权重为1的边，但如果V是大数，就不是一个好主意。不，这不是我的家庭作业，我只是在想。
-
我们有一个边带正权的有向图G(V，E)，作为源顶点s，目标点T。此外，最短的s-t路径包括图中的每一个其他顶点。我需要计算s和t之间的交替最短路径距离，以防某些边e∈e被删除。我想设计一个O(e^2logV)算法，它计算图G\e中所有e∈e的最短S-T路径距离。最后的输出应该是一个大小为E的数组，其中edge E的条目应该包含G\E中最短的S-T路径距离。
-
Dijkstra算法说 对于图中给定的源节点，算法找到该节点和其他节点之间的最短路径 我得到了算法来找到那个节点和其他节点之间的最短路径。但是我的问题是，如果我需要为Linkedin/facebook这样的大图找到两个特定节点（比如N1和N2）的最短路径，我需要计算该节点N1和领英上其他节点（用户，意味着十亿用户）之间的距离吗首先，将其存储在高速缓存中，然后在询问两个节点的最短距离时从高速缓存中返