# How to find the shortest path from some vertex in set $S$ to set $S'$

If i have a graph $G=(V,E)$, a subset of vertices $S \subset V$ and a second set of vertices $S' \subset (V\setminus S)$, what is the best way to find the shortest path connecting the two sets? That is, we are looking for a shortest path among all $S$-$S'$ paths. We can also assume all edge weights are positive.

Here is how I have approached this problem so far:

I already have the distance matrix information $(d)$ for graph $G$ which was calculated by applying the Floyd-Warshall algorithm in a previous operation.

I then iterate over all vertices in $S$ for each vertex in $S'$ and find the pair $(s_1,s_2)$ with the smallest value in matrix $d$.

Dijkstra's algorithm is then used to calculate the shortest path between $s_1$ and $s_2$, so connecting vertex sets $S$ and $S'$.

Is there a more efficient way of achieving this same outcome?

If all edge lengths are non-negative, then this can be solved in $O(|E| \lg |V|)$ time using a single invocation of Dijkstra's algorithm.

We're going to modify the graph slightly by adding a new vertex $s$. Also, add an edge of length 0 from $s$ to each vertex in $S$.

Next, run Dijkstra's algorithm, starting from the source vertex $s$. Dijkstra's algorithm will compute for you the distance from $s$ to every other vertex $v$, i.e., it will compute $d(s,v)$ for all $v \in V$. Note that $d(s,v)$ will be exactly the length of the shortest path from some vertex in $S$ to the vertex $v$.

Finally, compute $\min \{ d(s,v) : v \in S' \}$. This will be the length of the shortest path from some vertex in $S$ to some vertex in $S'$. That's your answer.

There's no need to run Floyd-Warshall.

If you can have negative edges, then it can be done in $O(|V| \cdot |E|)$ time. Simply replace Dijkstra's algorithm with the Bellman-Ford algorithm.

• You can even save calculating the minimum by adding another new vertex for $S'$. (One should note that the running time bound assumes $|E| \in \Omega(|V|)$, which is reasonable; $G$ can probably be assumed to be connected here.) – Raphael Jan 18 '16 at 7:56
• thanks for your answer, that makes a lot of sense. In regards to your point of not needing to run Floyd-Warshall, if i have already run floyd-warshall for something else and already have that information available, would it be faster to do a search on the distance graph? or not? because we have to run dijkstra anyway, is it just quicker to use the dummy vertex method? – guskenny83 Jan 18 '16 at 12:26
• @guskenny83, it depends. If you're already run Floyd-Warshall, finding the shortest path using its output will take $O(|S| \cdot |S'|)$ time to look up all $d[u,v]$ entries in the matrix for $u \in S, v \in S'$. That might be slower or faster than running Dijkstra's algorithm, depending upon the size of the sets $S,S'$ and the graph. For sparse graphs and large sets $S,S'$, it will be slower in the worst case. – D.W. Jan 18 '16 at 16:34