Finding $n$ paths on a graph with minimal overlapping Suppose I have a simple undirected graph $G = (V, E)$ and $n$ pairs of sources and destinations $(s_i, d_i)$.
Is there any existing algorithm to find a set of $n$ paths between those sources and destinations while trying to minimize edge overlapping between those $n$ paths? 
What are keywords I should use when searching? 
 A: There is an algorithm that builds set of edge-disjoint paths between given pairs of vertices using $O(n^2)$ time. If there was some algorithm for a weighted version of this problem then your problem would be solvable using this algorithm.
A: You can formulate this as a multicommodity flow problem and solve it via linear programming.  


*

*The commodities are $K = \{ s_i \} \times \{ d_i \} $.  

*Let $A$ be the arc set, with one arc in each direction for each edge in $E$. 


*

*For $(i,j)\in A$ and $k\in K$, let variable $x_{i,j}^k \ge 0$ be the flow along arc $(i,j)$ of commodity $k$.  


*Let variable $y_{i,j}\ge 0$ be the amount by which the total flow (in either direction) across edge $\{i,j\}\in E$ exceeds $1$. 

*Let $b_{i,k}$ be the supply at node $i$ of commodity $k$. We must have that:


*

*$b_{i,k} = 1$ for the source node of commodity $k$ (flow conservation at the source), 

*$b_{i,k} = -1$ for the sink node of commodity $k$ (flow conservation at the destination), and 

*$b_{i,k} = 0$ otherwise (flow conservation on transit nodes).  



The linear program breaks down to:
\begin{equation*}
\begin{array}{ll@{}ll}
\text{minimize}  & \displaystyle\sum_{\{i,j\}\in E} y_{i,j}  &\\
\text{subject to}& \displaystyle\sum_{k\in K} (x_{i,j}^k + x_{j,i}^k) &\le 1 + y_{i,j} &\forall\{i,j\}\in E\\
& \displaystyle\sum_j (x_{i,j}^k - x_{j,i}^k) &= 0   &\forall i\neq s_i,d_i\in V \text{ and }\forall k\in K\\
& \displaystyle\sum_j (x_{s_i,j}^k - x_{j,s_i}^k) &= 1   &\forall k\in K\\
& \displaystyle\sum_j (x_{d_i,j}^k - x_{j,d_i}^k) &= -1  &\forall k\in K\\
\end{array}
\end{equation*}
