0
$\begingroup$

Consider an unweighted, undirected, simple graph $G=(V,E)$. We have some subset $S \subseteq V$, and we want to determine the shortest distance from any vertex $v\in V$ to some vertex $s\in S$.

To be clear, each $v\in V$ has a distance $d_1, d_2,\dots , d_{|S|}$ to each $s\in S$, and we want to find the smallest value of all $d_1, d_2,\dots , d_{|S|}$, and do this for every $v\in V$. So every $s\in S$, for example, would have a distance of $0$.

The algorithm should run in $O(|V|+|E|)$ time. Note that this is independent of $|S|$. I was thinking of running simultaneous BFS's on each $s\in S$ and only assign a vertex a distance if it doesnt already have a distance estimate (i.e. no other node in $s$ reached to $v$ earlier). I'm not really sure how to make the runtime work out though, since we would have to cut off the BFS at some point to prevent a factor of $|S|$ in the runtime.

Also, this is not a homework problem, it's a question from a midterm from a class a few years ago that I am using to study for my final coming up, and the solutions are not available. Thanks for the help!

$\endgroup$
  • 1
    $\begingroup$ It looks like you might have inadvertently created two accounts. I encourage you to merge them and then register your account, to ensure you retain access to your question. $\endgroup$ – D.W. May 27 '16 at 4:22
1
$\begingroup$

Introduce a new node $s_0$ with edges to all $s \in S$ (but no others). Run BFS starting in $s_0$; the quantity you are looking for is

$\qquad\displaystyle \min_{s \in S} d(s, v) = d(s_0,v) - 1$

for every $v \in V$.

Nota bene: The idea extends to weighted graphs; you have to a) give the new edges weight $1$ and b) use an SSSPP algorithm, of course.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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