# A* is similar to Dijkstra with reduced cost

According to this Wikipedia article

If the heuristic $$h$$ satisfies the additional condition $$h(x) \leq d(x, y) + h(y)$$ for every edge $$(x, y)$$ of the graph (where $$d$$ denotes the length of that edge), then $$h$$ is called monotone, or consistent. In such a case, $$A^*$$ can be implemented more efficiently — roughly speaking, no node needs to be processed more than once (see closed set below) — and $$A^*$$ is equivalent to running Dijkstra's algorithm with the reduced cost $$d'(x, y) = d(x, y) + h(y) − h(x).$$

Can someone intuitively explain why the reduced cost is of this form ?

• Djikstra is actually a special case of A*. Think of Djikstra intuitively as A* with the heuristic cost being always zero. Nov 17, 2020 at 11:55

What you are doing when calculating $$d'(x,y)$$:
1. $$d(x,y)$$: calculating the original edge distance from $$x$$ to $$y$$
2. $$h(y)$$: plus the heuristic from $$y$$ to the goal
3. $$h(x)$$: minus the heuristic from $$x$$ to the goal
So, using this recalculation of the original edge-values ($$1.$$) in Dijkstra's algorithm you are inherently accounting for the heuristic component of A* by incorporating it ($$2.$$) into the value of the edge traversed, and discarding ($$3.$$) the accumulated previous heuristic values of previous nodes in the path.
The additional condition $$h(x) ≤ d(x, y) + h(y)$$ ensures the new edge-values are strictly positive.