# Converting between shortest path problems

Given a weighted digraph $$G$$, and collections of vertices $$R, S \subset V$$ , consider the problem of finding a shortest length path joining a vertex $$r\in R$$ to a vertex $$s\in S$$. Reduce this to the shortest path problem from a given vertex to all other vertices.

I have been looking at this question for a while and I'm struggling to articulate what I am thinking. Clearly I should start by taking some fixed $$a\in R$$ and finding all the shortest paths from a to every other vertex, but I am unsure how to create the paths from any other $$r\in R \setminus a$$ to $$s\in S$$ since I cannot guarantee they are the shortest.

• Do you need a many-one reduction or just a Turing reduction?
– Karl
May 24 at 14:53
• @Karl I think I am just supposed to reword the problem as I haven't encountered either reduction in this course. May 24 at 14:59
• Or maybe a polynomial time reduction? Can you make multiple calls to the shortest paths subroutine? I'd review your notes to make sure.
– Karl
May 24 at 14:59
• @Karl Polynomial Time is the only reduction we have covered but even then very briefly. Maybe that's why I'm struggling? The whole question is written above so I assume anything goes. May 24 at 15:01
• Yeah, "anything goes" isn't a well-defined task. If the problem says "reduce this", it should be clear what kind of reduction they're asking for. If it's a polynomial reduction, then (according to the Wikipedia definition) your solution can make multiple calls to the subroutine (e.g. one for every element of $R$).
– Karl
May 24 at 15:06

Introduce a dummy "supersource" node $$r_0$$ and a directed arc with weight $$0$$ from $$r_0$$ to each $$r\in R$$. Now solve a shortest path problem from $$r_0$$ to all vertices. Let $$d(r_0,i)$$ be the resulting shortest-path distances. For the path that corresponds to $$\min_{s\in S} d(r_0,s)$$, the first arc indicates which $$r\in R$$ to use.
A similar idea with an additional dummy supersink node $$s_0$$ further reduces the problem to a single-source, single-sink shortest path problem.