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!

Improve this question
$\endgroup$
1
  • 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$ Commented May 27, 2016 at 4:22

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.