Send N agents through directed graph with minimum cost

by mumuKabigon   Last Updated October 22, 2018 05:20 AM

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?



Related Questions


Tight example for capacitated vertex cover

Updated January 01, 2018 07:20 AM



Termination of Bellman-Ford algorithm

Updated October 28, 2018 15:20 PM