Send N agents through directed graph with minimum cost

32 Views Asked by At

I have a problem of sending N agents from source vertex 'src' to a destination vertex 'dst' of a directed graph which edges weights are increasing linear functions of n (n is the number of agents that already passed through that edge).

Graph image:

For example:

scenario 1
Agent1 , src->A->dst , cost = 1+(-1) = 0 
Agent2 , src->A->dst , cost = 2+2 = 4
Agent3 , src->A->dst , cost = 3+5 = 8
overall cost = 0 + 4 + 8 =12

scenario 2
Agent1 , src->A->B->C->A->dst , cost = 1+0+0.5+(-2)+(-1) = -1.5
Agent2 , src->A->dst , cost = 2+2 = 4
Agent3 , src->A->dst , cost = 3+5 = 8
overall cost = -1.5 + 4 + 8 = 10.5

How to find paths of every agents that minimize overall cost?