为什么使用Dijkstra算法而不是Best（Cheapest）First Search？ [英] Why use Dijkstra's algorithm instead of Best (Cheapest) First Search?

问题描述

从目前我读到的内容来看。 Best First Search 在寻找到达目标的最短路径方面似乎更快，因为Dijkstra的算法在遍历图时必须放松所有节点。什么使Dijkstra的算法比Best First Search更好？ 解决方案

编辑：您的编辑澄清您有兴趣在 Best-First Search 中，而不是 BFS 。

算法，它首先扩展最有前途的节点。非常类似于着名的 A *算法（实际上A *是特定的最佳优先搜索算法）。

Dijkstra是不知情的算法 - 当您不知道图时，应该使用它，并且无法估计从每个节点到目标。

请注意，当您使用启发式函数 h（v）= 0 对于每个 v $ b

另外，最佳搜索不是最佳搜索[不保证找到最短路径]，而且A *，如果您不使用可接受的启发式功能，而Dijkstra的算法总是最优的，因为它不会在任何启发式方法上进行中继。

结论：当您对图表有一定的知识时，Best-First Search应该优先于dijkstra，距离目标的距离。如果你不这样做 - 一个使用 h（v）= 0 的不知情的Best-First搜索，并且只在已经探索过的顶点上进行中继，则衰减进入Dijkstra算法。

此外，如果最优性很重要--Dijkstra的算法总是适合的，而只有当适当的启发式函数可用时才可以使用最佳优先搜索算法（特别是A *）。

---

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

BFS在 加权图 中失败。 / b>

示例：

  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--因为它更简单快捷（至少渐近地说）。

From what I have read so far. The Best First Search seems faster in terms of finding the shortest path to the goal because Dijkstra's algorithm has to relax all the nodes as it traverses the graph. What makes Dijkstra's algorithm better than Best First Search?

解决方案

EDIT: Your edit clarifies you are interested in Best-First Search, and not BFS.

Best-First Search is actually an informed algorithm, which expands the most promising node first. Very similar to the well known A* algorithm (actually A* is a specific best-first search algorithm).

Dijkstra is uninformed algorithm - it should be used when you have no knowledge on the graph, and cannot estimate the distance from each node to the target.

Note that A* (which is a s best-first search) decays into Dijkstra's algorithm when you use heuristic function h(v) = 0 for each v.

In addition, Best First Search is not optimal [not guaranteed to find the shortest path], and also A*, if you do not use an admissible heuristic function, while Dijkstra's algorithm is always optimal, since it does not relay on any heuristic.

Conclusion: Best-First Search should be prefered over dijkstra when you have some knowledge on the graph, and can estimate a distance from target. If you don't - an uninformed Best-First Search that uses h(v) = 0, and relays only on already explored vertices, decays into Dijkstra's algorithm.
Also, if optimality is important - Dijkstra's Algorithm always fit, while a best-first search algorithm (A* specifically) can be used only if an appropriate heuristic function is available.

---

Original answer - answering why to chose Dijkstra over BFS:

BFS fails when it comes to weighted graphs.

Example:

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

In here: w(A,B) = w(B,C) = 1, w(A,C) = 5.

BFS from A will return A->C as the shortest path, but for the weighted graph, it is a path of weight 5!!! while the shortest path is of weight 2: A->B->C.
Dijkstra's algorithm will not make this mistake, and return the shortest weighted path.

If your graph is unweighted - BFS is both optimal and complete - and should usually be prefered over dijkstra - both because it is simpler and faster (at least asymptotically speaking).

这篇关于为什么使用Dijkstra算法而不是Best（Cheapest）First Search？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！