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.

  • $\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


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.


You must log in to answer this question.

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