I'm stuck on coming up with an algorithm for the following scenario:
Say you run a set of k errands in an area represented by a directed weighted graph G. Each vertex v is a place, and there is an edge (u,v) weighted as $w_{uv}$ if it takes $w_{uv}$ minutes to go from u to v. Errands must be completed in order, and the ith errand is completed immediately upon visiting any vertex in the set $S_{i}$. You start at h, and you're trying to find the shortest path such that you do all errands in order. You cannot assume that the sets $S_{i}$ are strongly connected and that the sets are disjoint. You should only have to run one standard graph traversal algorithm per iteration for this to be an efficient solution.
I'm pretty sure this uses Dijkstra's algorithm, since we're trying to find the shortest path. I think I'm supposed to modify the graph so that each iteration only requires one traversal of Dijkstra's (or maybe a different algorithm, if I'm wrong). I'm struggling to figure out what that modification should be. I thought about removing edges when finished with an errand, but since we cant assume sets are disjoint, that wouldn't work. I thought about adding edges to make each set strongly connected, but that sounds like extra overhead. I also thought about running Dijkstra's twice -- but that only would be efficient if I already knew which vertex in the next destination set to go through.