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

Question

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

我的一个方法是使用双向BFS。通过双向BFS，我指的是从源节点应用两个BFS，另一个从目标节点开始。一旦我在两个树中发现任何相同的子节点，我就可以停止两个BFS。现在从源到该子节点的路径并集与从子节点到目标的路径将是我从源到目标的最短路径。

在维基百科和双向BFS描述的所有方法中，哪一种最适合我的图形呢？

- ravi

---

相关：https://dev59.com/cE3Sa4cB1Zd3GeqPtTvP - K Mehta

你可以使用A*搜索算法，但这涉及到使用启发式函数，更多是基于“人工智能”的方法。除此之外，Dijkstra算法是你最好的选择。 - K Mehta

如果性能不是太大的问题，我建议您选择Dijkstra算法。A*需要一个好的启发式函数才能发挥作用。 - K Mehta

我不能妥协性能。我应该在我的图中探索启发式算法。非常感谢。 - ravi

在这种情况下，您应该确保您的启发式算法是一致的，以确保获得最优解。 - K Mehta

Answer 1

如果有任何明显的启发式函数可以使用，或者您没有关于图形的更多可用信息，则取决于情况。

你的选择：

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

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

- bubersson

Answer 2

维基百科的文章为您详细解释了答案：

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

- Viktor Nordling

Answer 3

来自《算法导论》第二版第581页：

给定顶点 u 和 v，找到从 u 到 v 的最短路径。如果我们解决源顶点为 u 的单源问题，我们也可以解决这个问题。此外，在最坏情况下，没有已知的比最佳单源算法更快的算法来解决这个问题。

因此，坚持使用 Dijkstra 算法 :)

- Priyank Bhatnagar

Answer 4

你可以使用Dijkstra算法，并优化它的方式是停止探索已经比迄今为止找到的最短路径更长的路径。因为那些路径不会更短（前提是你的边没有负权重）。

- DerMike

---

我的图包含正权重。 - ravi

我不理解你的逻辑。Dijkstra算法总是选择最短的边。 - ravi