图形中从单个源到单个目标的最短路径

 

我的图形不包含将顶点连接到其自身的这种边。 两个顶点之间只有一条边。 从维基百科，我了解了一些基于给定条件用于计算最短路径的算法。 最着名的算法之一是Dijkstra's algorithm ，该Dijkstra's algorithm找出从源顶点到图中所有其他顶点的最短路径。
但通过使用Dijkstra's algorithm ，我不必探索所有的顶点，但是我的目标是找到从单一源到单个目标的最短路径。 我应该在这里使用哪种策略？ 所以我不需要去探索所有其他的顶点。

我的方法之一是使用bidirectional bfs 。 通过bidirectional bfs我的意思是从source node应用两个bfs ，另一个从destination node 。 只要在第一次时，我找不到任何相同child在两树，我可以同时停止bfs 。现在从源到孩子的路径union路径从小孩到目的地将是从源到目的地我的最短路径。

但是，出于维基百科和bidirectional bfs描述的所有方法，哪一个最适合我的图形？

这取决于是否有任何明显的启发式功能可以使用，或者如果您没有任何关于图形的更多可用信息。

您的选择是：

  • BFS：一般情况下，或者如果你不关心计算时间。
  • Dijkstra（Dijkstra“是”具有优先级队列的BFS）：如果你的边缘有权重/价格（非负），并且你关心CPU时间。
  • A *（A *“是”具有启发式功能的Dijkstra - 例如城市地图上的距离）：如果您希望平均速度非常快，但您必须提供良好的启发式功能。

    • 对于某些图形问题，可以使用动态编程或其他算法工具。 这取决于一种情况。 有关更多信息，请参阅http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index ...

    从算法简介（CLRS）第二版，第581页开始：

    查找给定顶点u和v从u到v的最短路径。 如果我们用源顶点u解决单源问题，我们也可以解决这个问题。 此外，没有人知道这个问题的算法在最坏的情况下比最好的单源算法渐近地运行得更快。

    所以，坚持Dijkstra的算法:)

    维基百科的文章为你解答了答案：

    如果我们只关心顶点源和目标之间的最短路径，我们可以在第13行终止搜索，如果u = target。

    链接地址: http://www.djcxy.com/p/35291.html

    上一篇: Shortest path from single source to single destination in a graph

    下一篇: Does dijkstras algorithm relax the edges of the shortest path in order?