You are given a directed graph G = (V, E) with non-negative edge weights w (u, v) representing the time it takes to go from a node u to v when u and v are directly connected. (We assume all w (u, v) < ∞ for simplicity.) Some subset F of vertices in G are pharmacies, while some other subset D are doctor offices. You live at a node s and have a medical emergency. You now need to go to some doctor office d ∈ D to get a prescription for the drug, then to some pharmacy f∈F, and finally back home. Recall that a proper output must be the full path described above. However, some paths are better than others. Solve the following variants of this problem, where each variant describes how to compare different valid paths when choosing the optimal path you are looking for. Each variant could be solved by one “clever” run of the Dijkstra’s algorithm, on an appropriate modification of our graph G. You have to explain your choice and state the resulting running time as a function of n (remember, we assume m = Θ(n2) here, as w(u, v) <∞).

 

(a) Assume only the distance from your homes to the doctor’s office matters (e.g., you need to get doctor’s emergency help asap, and the time it then takes to the pharmacy and back home are not important).

 

(b) Assume only the distance between the doctor office d and the pharmacy f matters. E.g., the doctor would perform some painful procedure, but does not have a tranquilizer to numb the subsequent pain. Thus, you must choose an office d ∈ D and pharmacy f ∈ F with the smallest distance between them, but you do not care how far d is from s or s is from f. (E.g., if there is a pharmacy in some doctor’s office in Antarctica, you do not mind going there, as the answer you care will be 0, even if you live in NYC.)

(Hint: Add an artificial source node s′ to G and compute the distance from s′ to “fill the blank” in your new graph.)

 

(c) Assume only the distance from the pharmacy f back to home s matters. E.g., the medicine must be administered by the pharmacist and has some quick side effect, so you must get to bed asap after taking the medicine in the pharmacy.

(Hint: Two solutions are possible: one does something to the edges of G, and the other again adds some artificial source similar to part (b).)

 

(d) Finally, assume that the overall trip time from s to d to f to s matters. Show how to combine the ideas in parts (a)-(c) to solve this variant.

(Hint: Make several “copies” of G and connect them “appropriately” by 0-weight edges. The copies will ensure that every valid path must pass through a doctor office followed by a pharmacy.)