Finding minimum operations to move ants through connected graph I am working on a project that requires to find the minimum number of steps to move ants from source to sink in a graph; one step is the movement of all ants from one node to the next of the graph. Only one ant per node
I already solved the problem of finding all possible disjoint paths. The issue I have is selecting the number of ants to send per path.
Here is an example:

every colour is a disjoint path. Given 12 ants, the best solution is to send 4 along gray, 3 along black, 3 along red, 1 along yellow and 1 along blue.
The only way that I found for now is a greedy solution but this will not scale well at all. I am not too good at math and I am sure there must be some smart formula to help me solve this problem. I tried to use the total length of the paths to help me solve it but I can't figure it out... Any help or resource is greatly appreciated
My current take:
I am calculating solutions by seeing how many ants go through the shortest path (grey) while one goes through a second one. So for "black" is 2 as len(n) / len(shortest). This helps me create proportions. Moreover I have the paths stored in increasing order. I do not send ants through a edge with increased len unless all previous edges are at capacity. if more edges have the same len I treat them as one (send same amount through them). This method seems to work but only with small tweaks in numbers when I find a solution. I feel like there is some sort of mistake but can't really pinpoint it.
 A: I'm thinking of this from the perspective of how many ants can you accommodate in $s$ steps.  Suppose your disjoint source-to-sink paths have lengths $(p_1, \ldots, p_n)$ listed in nondecreasing order.  The number of ants you can handle in $s$ steps is then, using the integer floor function,
$$ \left\lfloor \frac{s}{p_1} \right\rfloor + \cdots + \left\lfloor \frac{s}{p_n} \right\rfloor.$$
Your example has path lengths $(1,2,2,3,4)$.  In five steps, you can handle
$$ \left\lfloor \frac{5}{1} \right\rfloor + \left\lfloor \frac{5}{2} \right\rfloor + \left\lfloor \frac{5}{2} \right\rfloor + \left\lfloor \frac{5}{3} \right\rfloor + \left\lfloor \frac{5}{4} \right\rfloor = 5+2+2+1+1 = 11$$
ants, while with $s=6$ steps you can handle
$$ \left\lfloor \frac{6}{1} \right\rfloor + \left\lfloor \frac{6}{2} \right\rfloor + \left\lfloor \frac{6}{2} \right\rfloor + \left\lfloor \frac{6}{3} \right\rfloor + \left\lfloor \frac{6}{4} \right\rfloor = 6+3+3+2+1 = 15.$$
So for 12 ants, you need 6 steps.  To make something algorithmic, set up the plan for the optimal 15 ants in 6 steps and then ignore, say, the first 3, giving here (3 gray, 3 black, 3 red, 2 yellow, 1 blue).  Or the last 3, giving (6 gray, 3 black, 3 red).
In general, compute the $\lfloor s/p_i \rfloor$ sum for increasing $s$ until you first reach or exceed the number of ants you need, make the allocation from the formula for the optimal number that can be handled, and then ignore the appropriate number of ants.
