为什么使用 Dijkstra 算法而不是最佳（最便宜）优先搜索？

从我到目前为止所读到的来看。这最佳优先搜索 https://en.wikipedia.org/wiki/Best-first_search在找到到达目标的最短路径方面似乎更快，因为 Dijkstra 算法在遍历图时必须放松所有节点。是什么让 Dijkstra 算法比最佳优先搜索更好？

EDIT：您的编辑表明您感兴趣最佳优先搜索， 并不是BFS.

最佳优先搜索实际上是一种知情算法，首先扩展最有前途的节点。与众所周知的非常相似A*算法 http://en.wikipedia.org/wiki/A*_search_algorithm（实际上A*是一种特定的最佳优先搜索算法）。

Dijkstra 是无知算法- 当您对图不了解，并且无法估计每个节点到目标的距离时，应该使用它。

请注意，当您使用 A*（最佳优先搜索）时，它会衰减为 Dijkstra 算法启发式函数 http://en.wikipedia.org/wiki/Heuristic_function h(v) = 0对于每个v.

此外，最佳优先搜索并非最优[不保证找到最短路径]，还有 A*，如果你不使用允许的启发函数 http://en.wikipedia.org/wiki/Admissible_heuristic，而 Dijkstra 算法始终是最优的，因为它不依赖于任何启发式算法。

结论：当您对图表有一定了解并且可以估计距目标的距离时，最佳优先搜索应该优于 dijkstra。如果您不这样做 - 不知情的最佳优先搜索使用h(v) = 0，并且仅中继已经探索过的顶点，衰减为 Dijkstra 算法。
此外，如果最优性很重要 - Dijkstra 算法始终适用，而只有在适当的启发式函数可用时才能使用最佳优先搜索算法（特别是 A*）。

原始答案 - 回答为什么选择 Dijkstra 而不是 BFS：

当涉及到以下情况时，BFS 会失败加权图 http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Weighted_graphs_and_networks.

Example:

     A
   /   \
  1     5
 /       \
B----1----C

在这里：w(A,B) = w(B,C) = 1, w(A,C) = 5.

来自 A 的 BFS 将返回A->C作为最短路径，但对于加权图来说，它是权重为5的路径！而最短路径的权重为 2：A->B->C.
Dijkstra算法不会犯这个错误，并且返回最短加权路径。

如果您的图未加权 - BFS 既是最优的又是完整的- 通常应该优于 dijkstra - 两者都是因为它更简单且更快（至少渐近地说）。