$2\mathrm{.}4\mathrm{.}4.$ Sometimes the number of decisions is not the appropriate measure to use in looking for a goal. For example, suppose we have a map of highways with mileages between highway intersections. The goal is to find the shortest route between intersections A and $B.$

$($a$)$ Explain how a search graph can be constructed where the vertices are intersections and each edge has a "cost" equal to the number of miles.

$($b$)$ Show how this leads to a search tree with $($a$)$ the root labeled $A,($b$)$ all goals labeled $B,($c$)$ a cost for each edge equal to mileage, and $($d$)$ the aim of finding that path from the root to a $B$ for which the sum of the edge weights is a minimum. We can associate with each vertex $v$ a cost $C(v)$ that equals the sum of the edge weights on the path from the root to $v.($The path is unique since we are in a tree.$)$

$($c$)$ We can generalize the previous part to a search tree in which each vertex $v$ has an associated cost $C(v)$ and costs increase as we move downward. Modify the breadth$-$first algorithm to produce a "best$-$first" algorithm that finds the least$-$cost goal.

Hint. Always remove the vertex with the least cost from $$ and do not check whether a vertex is a goal until you remove it from $.$

$($d$)$ Prove that the algorithm you have given does in fact find the least cost goal.