8
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Raphael ♦
    Jan 18, 2016 at 7:56
  • $\begingroup$ 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? $\endgroup$
    – guskenny83
    Jan 18, 2016 at 12:26
  • 1
    $\begingroup$ @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. $\endgroup$
    – D.W. ♦
    Jan 18, 2016 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.