Dijkstra算法VS A *对于权图

Question

我试图找出用哪种算法来获得一个目标节点从给定的起始节点的最低成本路径。

A ----5---- B ---3--- C 
|   | 
|   /
D ----1-----E ------10------ F 

我一直在寻找到Dijkstra和A *，因为他们都给这样的问题提供了最优解决方案。我理解的方式是，Dijkstra只是一个启发式为0的A *。我已经实现了Dijkstra算法，但想知道是否可以使用A *。在如上所述的非常简单的图中（没有任何其他信息），是否存在A *可以用来提供比Dijkstra更好的结果的可容许启发，还是Dijkstra最优化的算法？

Answer 1

如果没有适合的图形，那么你必须选择Dijkstra算法的内容启发式的知识。

A *是为路线图，其中用于道路距离的约束加上了直接的距离总是比通过其他节点会更短的开发。该约束不适用于一般加权图。

如果你不知道你的图形的内容，例如一个附加的约束/启发式，那么你必须使用Dijkstra算法

考虑进一步保持这一路线图图是如此之大，这是值得使用一个*。 如果你的图形不是很大，那么可能它甚至不值得考虑是否找到任何启​​发式。这种错误的启发式甚至会让事情变得更糟。

所以，你可以使用Dijkstra算法，并且只有当你有一个性能问题，你可以开始考虑找一个启发。