New Algorithm

Change EXTRACT-MIN in Dijkstra's to pick out the node u with the smallest value of d[u]+h(u). [Note, at the smallest value of d[u]+h(u), $f(u) =\delta(s,u)+h(u) = d[u]+h(u)$ because of monotonicity.]

Idea:

• The quantity f(u) is an underestimate of the total distance from s to t through u (true distance from s to u plus an underestimate of the distance from u to t).
• By focussing the search on the nodes with the smallest value of f(u), we are likely to be doing work along the true shortest path.

This is called A^*.