Important Properties

For the nice formal properties to hold, we need h to satisfy a few properties:

• Admissibility: For any node u, $0\le h(u)\le \delta(u,t)$.
• Monotonicity (triangle inequality): For any pair of nodes u and v, $h(u) \le h(v) + w((u,v))$.
• Destination: h(t) = 0 (follows from admissibility).

Here are some useful definitions.

• $f^*(u) = \delta(s,u)+\delta(u,t)$: shortest diverted path.
• $f(u) = h(u) + \delta(u,t)$: estimated distance.