Question: In order to speed up Dijkstra's algorithm for certain classes of graphs, let's see if we can use some auxiliary information. Suppose we want to find a shortest-path from u to v, and we have a *valid* heuristic, i.e.: For every node w, we have a value a(w) such that the distance from w to v in G is at least a(w) for all nodes w. Recall that Dijkstra's algorithm will maintain a set S of nodes whose distances to u are known, and once v is in S, we will have the correct distance from u to v. The node w added to S at every step is the node not in S with smallest label d[w].
Instead, let's add the node with the smallest value d[w]+a(w).
Prove that when v is added to S, we can stop and recover a shortest u-v path.
Describe each and every question in depth with examples.