I was reading about how to use $A^*$ and was told that:A heuristic is admissible if $h(u) \leq \delta(u,t)$, where $\delta(u,t)$ function indicates that the shortest path from $u$ to $t$.I was wondering why such a condition guarantees that the shortest paths can still be computed.Its clear to me if the heuristic is defined as with the help of a potential function $\lambda(u)$:$$ h(u) = \lambda(u) - \lambda(s) $$and the new weights are defined as (i.e. the potential function is feasible):$$ w^*(u,v) = w(u,v) + h(u) = w(u,v) + \lambda(u) - \lambda(s) $$then if we have $w^*(u,v) \geq 0$ with that heuristic then its clear that shortest paths are retained (because of telescoping series). However, otherwise, I can't see why admissible function would retain shortest paths or what the motivation is to use admissible function with the property $h(u) \leq \delta(u,t)$. Why is that?Usually heuristics tilt search algorithms to better paths, how do admissible function attain this?
Why do admissible functions allow $A^*$ to retain correct shortest path computations?
algorithms;shortest path;heuristics