我的图不包含将顶点连接到自身的边。两个顶点之间只有一条边。来自 Wikipedia我了解了一些用于根据给定条件计算最短路径的算法。最著名的算法之一是 Dijkstra 算法，它寻找从源顶点到图中所有其他顶点的最短路径。
但是通过使用 Dijkstra 算法，我没有必要探索所有的顶点，但是我的目标只是找到从单一源到单一目的地的最短路径。我应该在这里使用哪种策略？这样我就不需要探索所有其他顶点。
我的方法之一是使用双向bfs。 双向 bfs 我的意思是应用两个 bfs，一个来自 source node，另一个来自 destination node。当我第一次在两棵树中找到任何相同的 child 时，我可以停止这两个 bfs 。现在从源到那个 child 的路径 union 从 child 到目的地的路径将是我从源到目的地的最短路径。
但在维基百科和双向 bfs 描述的所有方法中，哪种方法最适合我的图？
最佳答案
这取决于您是否可以使用任何明显的启发式函数，或者您是否没有关于图表的任何进一步可用信息。
您的选择是:
- BFS:在一般情况下，或者如果您不太关心计算时间。
- Dijkstra(Dijkstra "is"具有优先队列的 BFS):如果你的边有权重/价格(非负)并且你关心 CPU 时间。
- A*(A*"is"具有启发式函数的 Dijkstra——例如城市 map 上的距离):如果您希望它在一般情况下非常快，但您必须提供良好的启发式函数。
对于某些图形问题，可以使用动态规划或其他算法工具。这取决于情况。可以在来自 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index 的教程中找到更多信息。 ...
关于algorithm - 图中从单一源到单一目的地的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10053931/