Problem $5-2()$

$10$ points

You live in a dorm at node $s$ of a weighted directed graph $G=(V,E)$ with non$-$negative weights

and $n=|V|$ and $m=|E|.$ One day, your friend who dorms at node $h$ falls sick and needs your

help. Naturally, you want to get from $s$ to $h$ as soon as possible, but you are supposed to stop by

a pharmacy. You can get pills at any pharmacy, and the pharmacies form a subset of the vertices

PsubV. Thus, starting at $s,$ you must go to some node pinP of your choice, and then head from

$p$ to $h$ using the shortest total route possible.

$($a$)(4$ points$)$ Think of the problem as being subdivided into two parts, first of computing

shortest distances to all pharmacies pinP. And second of computing the shortest path from

every pharmacy pinP to $h.$ Solve the problem using calls to the Dijkstra's algorithm. $($Hint:

Think about how we can manipulate the graph to solve the second subpart in one call.$)$

$($b$)(6$ points$)$ Define a new graph $G^{\text{'}}$ on at most $2n$ vertices and at most $2m+n$ edges $($and

"appropriate" weights on these edges$),$ so that the original problem can be solved using a

single Dijkstra call on $G^{\text{'}}.$