<p>What you are doing when calculating <span class="math-container">$d'(x,y)$</span>:</p>

<ol>
<li><span class="math-container">$d(x,y)$</span>: calculating the original edge distance from <span class="math-container">$x$</span> to <span class="math-container">$y$</span></li>
<li><span class="math-container">$h(y)$</span>: plus the heuristic from <span class="math-container">$y$</span> to the goal</li>
<li><span class="math-container">$h(x)$</span>: minus the heuristic from <span class="math-container">$x$</span> to the goal</li>
</ol>

<p>So, using this recalculation of the original edge-values (<span class="math-container">$1.$</span>) in Dijkstra's algorithm you are inherently accounting for the heuristic component of A* by incorporating it (<span class="math-container">$2.$</span>) into the value of the edge traversed, and discarding (<span class="math-container">$3.$</span>) the accumulated previous heuristic values of previous nodes in the path.</p>

<p>The additional condition <span class="math-container">$h(x) ≤ d(x, y) + h(y)$</span> ensures the new edge-values are strictly positive.</p>

CC BY-SA 4.0
2020-04-24T13:05:11.017Z
2020-04-24T14:06:15.103Z
2020-04-24T14:06:15.103Z
brazofuerte
<p>According to <a href="https://en.wikipedia.org/wiki/A*_search_algorithm#Description" rel="nofollow noreferrer">this Wikipedia article</a></p>
<blockquote>
<p>If the heuristic <span class="math-container">$h$</span> satisfies the additional condition <span class="math-container">$h(x) \leq d(x, y) + h(y)$</span> for every edge <span class="math-container">$(x, y)$</span> of the graph (where <span class="math-container">$d$</span> denotes the length of that edge), then <span class="math-container">$h$</span> is called monotone, or consistent. In such a case, <span class="math-container">$A^*$</span> can be implemented more efficiently — roughly speaking, no node needs to be processed more than once (see closed set below) — and <span class="math-container">$A^*$</span> is equivalent to running Dijkstra's algorithm with the reduced cost <span class="math-container">$d'(x, y) = d(x, y) + h(y) − h(x).$</span></p>
</blockquote>
<p>Can someone intuitively explain why the reduced cost is of this form ?</p>

CC BY-SA 4.0
2020-11-17T11:55:10.457Z
Djikstra is actually a special case of A*.
Think of Djikstra intuitively as A* with the heuristic cost being always zero.
Valentin Metz
<comparison><search><heuristics><a-star><dijkstras-algorithm>
A* is similar to Dijkstra with reduced cost
Shrey Shrivastava
# A* is similar to Dijkstra with reduced cost

(Asked by: username_0 on 2019-05-24)

According to [this Wikipedia article](https://en.wikipedia.org/wiki/A*_search_algorithm#Description)

> 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 ?

**Tags:** comparison, search, heuristics, a-star, dijkstras-algorithm

> **Comments:**
> **username_1**: Djikstra is actually a special case of A*. Think of Djikstra intuitively as A* with the heuristic cost being always zero.  

---

## 1 answers

### Answer by username_2 on 2020-04-24. Score: 1

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.


---

