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