我正在尝试分析 A* 和 Dijkstra 算法的速度。我正在使用http://www.boost.org/doc/libs/1_38_0/libs/graph/example/astar-cities.cpp和http://www.boost.org/doc/libs/1_50_0提供的代码/libs/graph/doc/dijkstra_shortest_paths.html。我尝试了一个包含 500 条边和 300 个节点的简单图。
我期待 A* 比 Dijkstra 表现更好，因为在 Dijkstra 中找到了从源顶点到每个其他顶点的最短距离。另一方面，在 A* 中，只找到到目标节点的最短距离。
然而，分析表明 Dijkstra 的表现略好于 A*。有可能还是我错过了什么？
Djikstra 的算法使用队列，而 A* 使用优先级队列。一般来说，队列将比优先级队列执行得更好（例如，使用链表或循环数组O(1)从队列中入队/出队是，而使用堆从优先级队列中入队/出队是O(log n)）。
然而，一般来说，这种微小差异导致 A* 运行速度比 Djikstra 慢的情况往往是两种算法无论如何都运行得非常快的情况——在小迷宫和只需要考虑少量路径的迷宫中（例如作为一个曲折的迷宫）。在较慢的情况下（在没有障碍物的开阔地带），A * 应该跑得更快。
由于您的案例有 300 个节点，因此您的代码很可能有问题。没有看到它，我们无法为您提供任何进一步的帮助。
听起来您的启发式方法不准确，或者您的 A* 在数据集上执行的传递次数比 Dijkstra 多（同样，可能是由于启发式方法）。
编辑：例如，如果您的 A* 实现遍历整个数据集并且每次只扩展一个节点（具有最佳启发式的节点），那么它可以执行比 Dijkstra更多的传递（它会尽快扩展每个节点） ）。
如果可能，请分析每个算法执行的遍数，而不是只查看整体处理时间。