# Find shortest paths between two groups of a graph

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.

• Is it necessary that these paths are disjoint? Feb 11, 2021 at 13:23
• No. Paths don’t have to be disjoint Feb 11, 2021 at 13:35

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$$.