1
$\begingroup$

Let $\ G(V,E) $ be a simple directed graph with non-negative edges weights. Given a group of vertices $\ A \subset V $ I need to find an algorithm that for every vertex $\ v \in V \setminus A $ , it will find the shortest path possible from any vertex in $\ A $ to that vertex $\ v $

My attempt:

$\ U := V \setminus A $

I will set a new array of size $\ |U| $ with all of its values set to $\ \infty $ and then for every vertex $\ v_1 \in A $ I will run a modified BFS where BFS iteration will stop if it is needed to go through another vertex in $\ A $ . check the result of the BFS for that $\ v_1 $ and update my initial array with distances if necessary.

$\endgroup$
2
  • $\begingroup$ Is it necessary that these paths are disjoint? $\endgroup$ Feb 11, 2021 at 13:23
  • 1
    $\begingroup$ No. Paths don’t have to be disjoint $\endgroup$
    – bm1125
    Feb 11, 2021 at 13:35

1 Answer 1

1
$\begingroup$

Since your edge weights are all positive and you are not stating that these paths must be disjoint, you can just apply Dijsktra‘s algorithm for every vertex in $A$ to every vertex in $V \setminus A$.

The algorithm works for directed graphs, too. This is discussed here. An implementation can be found here.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .