图中从单个源到单个目的地的最短路径
我的图形不包含这样的边，它们将顶点连接到自身。两个顶点之间只有一条边。通过维基百科，我了解了一些基于给定条件计算最短路径的算法。最著名的算法之一是Dijkstra的算法，它可以找到从源顶点到图中所有其他顶点的最短路径
但是通过使用Dijkstra的算法，我没有必要探索所有的顶点，但是我的目标只是找到从单一来源到单一目的地的最短路径。我应该在这里使用哪种策略？所以我不需要探索所有其他顶点。
我的方法之一是使用双向bfs。通过双向bfs我的意思是应用两个bfs，一个来自源节点，另一个来自目标节点。当我第一次在这两个树中找到任何相同的子项时，我就可以停止这两个bfs。现在，从源到子union从子到目标的路径将是我从源到目标的最短路径。
但是在维基百科和双向bfs所描述的所有方法中，哪一种最适合我的图表？
共有3个答案
维基百科的这篇文章为你详细说明了答案：
如果我们只对源和目标顶点之间的最短路径感兴趣，如果u=目标，我们可以在第13行终止搜索。
摘自《算法导论》（CLRS）第二版，第581页：
对于给定的顶点u和v，找到从u到v的最短路径。如果我们用源顶点u解决单源问题，我们也解决了这个问题。此外，已知该问题的任何算法在最坏情况下都不会比最好的单源算法运行得更快。
所以，坚持Dijkstra的算法：）
这取决于是否有任何明显的启发式函数可以使用，或者是否没有关于图形的任何进一步可用信息。
您的选择是：
- BFS：一般情况下，或者如果你不太在乎计算时间
对于一些图形问题，可以使用动态规划或其他算法工具。这取决于情况。更多信息可在以下网站的教程中找到：http://community.topcoder.com/tc?module=Static
-
下面的堆栈溢出问题 我尝试了在语句中使用两个重复的多个构造，但无法为每个起始顶点获得独立的。我也在使用平台，因此它限制了Gremlin的使用，其中不允许使用循环/脚本。所有gremlin查询必须以并由与链接在一起的命令组成 https://docs.aws.amazon.com/neptune/latest/userguide/access-graph-gremlin-differences.ht
-
import scala.reflect.ClassTag import org.apache.spark.graphx._ /** * Computes shortest paths to the given set of landmark vertices, returning a graph where each * vertex attribute is a map containin
-
我试图用BFS找到无向加权图的单源最短路径算法。 我想出了一个解决方案，将每个边权重转换成顶点之间的x边，每个新边权重为1，然后运行BFS。我会得到一棵新的BFS树，因为它是一棵树，所以从根节点到每个其他顶点只有1条路径。 我遇到的问题是试图对以下算法进行分析。每个边都需要访问一次，然后根据其权重划分为相应数量的边。然后我们需要找到新图的BFS。 访问每条边的成本是O（m），其中m是每一条边访问一
-
好的，我发布这个问题是因为这个练习： 我们能否修改Dijkstra的算法，通过变极小为极大来解决单源最长路问题？如果是，那么证明你的算法是正确的。如果没有，那么提供一个反例。 将距离数组初始化为minint 将更改为 然后我做了一些研究来验证我的答案。我发现了这个帖子： 从源到DAG中某些节点之间的最长路径
-
自定义地图上两点，绘制出两点直接的路径。使用MKPolyline绘制路径，支持长按（long press）地图自定义两点坐标。 作者说：参照http://code.google.com/p/ashiphone/downloads/detail?name=MapWithRoutes.zip
-
我想写一个算法，在有向图和无向图中找到两个特定顶点（源和目标）之间的最短路径。 我知道dijkstra算法，该算法用于寻找所有最短路径图。但是你会修改这个算法，只找到两个顶点之间的最短路径吗？