Suppose we have a weighted undirected graph $G(V,E)$. We are given the information that $V_a \cap V_b = \emptyset$ and $V_a,V_b \subset V$.

We want to find paths from all vertices in $V_a$ to all vertices in $V_b$ given the following conditions:

- Primary objective: paths minimize the number of shared edges
- Secondary objective: sum of weighted path lengths are minimized
- Sharing an edge gives a penalty equivalent to the weight of the shared edge
- Consider the following example:
- If path $s_1 - t_1$, $s_2 - t_1$, and $s_3 - t_1$ all use edge $e_2$ then the penalty is $3\cdot weight(e_2)$.

- Consider the following example:
- Paths from any particular $s \in V_a$ to all $t \in V_b$ do not acquire a penalty for overlapping with other paths from that particular $s$. That is to say paths from $s_i$ to $t_j$ for all $t_j \in V_b$ cannot acquire a penalty from each other.
- Consider the following examples:
- If path from $s_1$ to $t_1$ uses edges $e_1, e_2, e_3$ and path from $s_1$ to $t_2$ uses the edges $e_1, e_2, e_4$, then there is no penalty.
- If path from $s_1$ to $t_1$ uses edges $e_1, e_2, e_3$ and path from $s_2$ to $t_2$ uses the edges $e_1, e_2, e_4$, then there is a penalty of $\mathit{weight}(e_1) + \mathit{weight}(e_2)$.

- Consider the following examples:

**Pictured Example:**

In the pictured example we can find the following solutions for each of the desired six paths:

- $s_1 - t_1$: $s_1,a,t_1$
- $s_1 - t_2$: $s_1,a,t_2$
- note there is no penalty for sharing the edge $(s_1,a)$ because both paths so far both start from $s_1$

- $s_2 - t_1$: $s_2,b,a,t_1$
- Note this would have a penalty for sharing edge $(a,t_1)$ with the path from $s_1-t_1$

- $s_2 - t_2$: $s_2,b,a,t_2$
- Note there is no penalty from this path

- $s_3 - t_1$: $s_3,c,t_1$
- Note this has no penalty and we could have chosen path $s_3,c,d,t_1$ for no penalty as well, but it is a longer path so we don't choose it

- $s_3 - t_2$: $s_3,c,d,t_2$
- Note this has no penalty no matter what path was chosen for $s_2-t_1$

The practical application of this problem is loosely defined. These constraints are not rigid if they cause too many complications. For example, instead of having the penalty in the first example being $3 \cdot \mathit{weight}(e_3)$ it might be acceptable to have the penalty as $\mathit{weight}(e_3)$. I'm mostly looking for new ideas to handle this or a slight variation of this problem.

This is an extension to Algorithm for finding minimally overlapping paths in a graph