dijkstra的算法是f(n) = g(n)
而A*是f(n) = g(n) + h(n)。
g（n）是从起始节点到n的路径的成本。
h（n）是一个启发式函数，用于估计从n到目标的最便宜路径的成本。
需要g（n）吗？没有g（n）它就找不到最短路径吗？
为什么A*需要g（n）？
最佳答案
我们需要g(n)
考虑这样的情况，对于目标的某条给定路径上的所有节点（这是一个完全有效的，即可接受的，启发式的），当h(n)是0时，对于所有其他节点都是非零的。
如果我们忽略到目前为止的代价（g(n)），很明显，无论实际代价是多少，我们都会选择此路径上的节点，因此我们最终使用的路径可能比其他路径的代价要大得多。
start
g(n)=0 O --
5 | \ 1
h(n)=0,g(n)=5 O O h(n)=1,g(n)=1
5 | / 1
h(n)=0,g(n)=10 O --
goal
在上面的例子中，我们将选择左边的节点，然后选择目标，因为这两个节点都
h(n) = 0（它大于右边节点的h(n) = 1）。这将为我们提供一条成本10的路径，其中最便宜的路径包括选择右边的节点，成本2。这也许是一个极端的例子，但同样的想法也适用于许多其他情况。例如，您还可以将10添加到我的示例中的所有值中，并使它成为一个较大图形的一部分，但它仍然会错误地选择右侧上方的左侧。
这里更一般的结论是，您可以在2个节点
n1和n2之间选择h(n1) < h(n2)位置，因此我们将选择n1，但是n2是在最便宜的路径上，而不是n1。如果包含
g(n)，我们也可以选择错误的节点但是，在这种情况下，对于路径上的一些节点，包括n，n1将大于最便宜的路径（在最坏的情况下f(n)将是目标，n将是通过f(n)到达它的真正成本，这显然比实际最便宜的路径更昂贵），因此也大于n1（因为启发式需要低估成本），因此我们将在达到目标之前探索f(n2)。如果
n2是真实成本（而不是估算）那么我们确实不需要
h(n)。但在这种情况下，仅考虑
g(n)将使其成为贪婪算法（假设边缘权重为非负），因为h(n)对于我们选择的每个节点都将减少（因为我们正在接近目标），所以在开始节点，我们将选择最优路径上的节点（因为它将具有最低的h(n)），从那里开始，我们将继续在最佳路径上选择节点。