Let's consider a weighted graph $G = (V,E)$ not directed. In this graph, there are several sinks $S$, which are vertices.
Let's consider one vertex $V$ of this graph (which is a source). The problem is twofold:
- Can we compute the maximum number of vertex-disjoint paths $M_{max}$ given a constraint on the cost $C_{max}$ and the number of edges $E_{max}$? If yes how?
- Can we get the $N$ sets of vertex-disjoint paths (with $1$ to $M_{max}$ paths in each set)? If yes how?
I'm quite novice in the graph theory field, I just have experience with Dijkstra, which is a sub-problem of the minimum-cost flow problem, itself being a sub-problem of the multicommodity flow problem. It seems to me the problem exposed here is a minimum cost multi-commodity flow problem with only $1$ source and the $2$ constraints exposed above. I might be wrong. Could you direct me in the right direction to solve this problem? I did not see any question in math.SE adressing the multi-sink issue, while there are answers for a mono-source/mono-sink issue here or here.
The best thing would be if you direct me towards a library that solves this kind of problem :)