3

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

我的一种方法是使用bidirectional bfs. bidirectional bfs我的意思是申请两个bfs来自，source node另一个来自。destination node当我第一次child在两棵树中找到相同的东西时，我可以停止两者bfs。现在从源到子union路径从子路径到目的地的路径将是我从源到目的地的最短路径。

但是在 Wikipedia 和 描述的所有方法中 bidirectional bfs，哪一种最适合我的图表？

4

4 回答 4

4

这取决于您是否可以使用任何明显的启发式函数，或者您是否没有关于图表的任何进一步可用信息。

您的选择是：

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

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

于 2012-04-07T11:29:47.090 回答
1

来自算法简介 (CLRS) 第二版，第 581 页：

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

所以，坚持 Dijkstra 的算法 :)

于 2012-04-07T11:14:29.440 回答
1

维基百科文章为您说明了答案：

If we are only interested in a shortest path between vertices source and target, we can terminate the search at line 13 if u = target.

于 2013-06-24T12:13:05.997 回答
0

您可以使用 Dijkstra 的算法并对其进行优化，以停止探索已经比迄今为止发现的最短路径更长的路径。因为这些不会更短（前提是您的边缘没有负重）。

于 2012-04-07T11:16:15.380 回答