0
$\begingroup$

Which algorithm do I use and how much does it cost if I have to:

Calculate all distances in an undirected and unweighted graph from two sources to all nodes.

I think the most appropriate algorithm is a BFS(G,s) with cost T(n)= O(V+E) where V= (number of nodes) and E=(number of arcs). The algorithm is the one in the figure. In this algorithm, however, only one source is considered. So it wouldn't answer the question. What would be the right answer and what the cost?

enter image description here

$\endgroup$
1
  • $\begingroup$ Hint: if $f(n,m)$ is a positive function, then $2\cdot f(n,m) = O(f(n,m))$. $\endgroup$
    – Steven
    Commented Feb 19, 2023 at 11:27

1 Answer 1

0
$\begingroup$

Approach:

  1. Run $BFS(v_{1})$.
  2. Run $BFS(v_{2})$.

With $v_1$ and $v_2$ being your two sources.

Complexity:

$O(|V|+|E|) + O(|V|+|E|) = O(|V|+|E|).$

As long as you have a constant $c$, then $c\times f(n) = O(f(n))$.

$\endgroup$

Your Answer

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

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