为什么使用Dijkstra的算法而不是Best(最便宜的)First Search？

Question

从我到目前为止所读到的.在最佳优先搜索似乎更快寻找到终点的最短路径,因为Dijkstra算法有放松的所有节点,因为它穿越图形的条款.是什么让Dijkstra的算法比Best First Search更好？

Answer 1

编辑:您的编辑说明您对Best-First Search感兴趣,而不是BFS.

Best-First Search实际上是一种知情算法,它首先扩展了最有希望的节点.非常类似于众所周知的A*算法(实际上A*是特定的最佳优先搜索算法).

Dijkstra是一种不知情的算法 - 它应该在您对图表不了解时使用,并且无法估计从每个节点到目标的距离.

请注意,当您为每个算法使用启发式函数 时,A*(这是最佳优先搜索)会衰减为Dijkstra的算法.h(v) = 0v

此外,如果您不使用可接受的启发式函数,则Best First Search不是最优 [不保证找到最短路径],也不是A*,而Dijkstra的算法总是最优的,因为它不会在任何启发式中继.

结论:当你对图表有一些了解时,应该优先考虑最佳优先搜索,并且可以估计与目标的距离.如果你不这样做 - 一个不知情的最佳优先搜索使用h(v) = 0,并且只对已经探索过的顶点进行中继,则会衰减到Dijkstra的算法中.
此外,如果最优性很重要 - Dijkstra的算法总是适合,而最佳优先搜索算法(A*具体)只有在适当的启发式函数可用时才能使用.

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

对于加权图, BFS失败.

例:

     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 - 因为它更简单,更快(至少渐渐地说).