Cheap and Secure Web Hosting Provider : See Now

[Solved]: How to find the shortest path from some vertex in set $S$ to set $S'$

, , No Comments
Problem Detail: 

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?

Asked By : guskenny83

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51991

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback