Dijkstra算法比DFS快吗？

Question

也许这是一个愚蠢的问题，但我一直在使用 Dijkstra 算法进行一些与图相关的实现。现在我必须实现一个脚本，我需要在其中找到节点之间的距离。使用权重等于 1 的 Dijkstra 算法或实施 DFS，Whick 是更好的选择？

Answer 1

Dijkstra 的所有权重相等的算法完全等同于 BFS（不是 DFS）。 DFS 不适合寻找最短路径，因为它首先探索最长的路径，但 BFS 适合。

如果您事先知道所有权重都相等，那么使用优先级队列和实现完整的 Dijkstra 就没有意义；您可以使用普通队列并以更少的代码和更少的开销获得 BFS。