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

Question

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

我的方法之一是使用bidirectional bfs. 我的bidirectional bfs意思是应用两个，bfs一个来自source node，另一个来自destination node。一旦我第一次child在两棵树中找到相同的内容，我就可以停止两者bfs。现在从源到子union路径的路径从子到目的地将是我从源到目的地的最短路径。

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

Answer 1

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

您的选择是：

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

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