You can try the greedy method. So
If A owes money to B and B owes C then A owes C the minimum of (A->B, B->C). And A->B -= min(A->B, B->C). If after this operation A->B becomes zero
then you remove it. Loop till you cannot perform any further operation ie, there're no cycles
in the graph.:
do{
bool stop = true;
G.init() // initialize some sort of edge iterator
while(edge = G.nextedge()){ //assuming nextedge will terminate after going through all edges once
foreach(outedge in edge.Dest.Outedges){ //If there's any node to 'move' the cost
minowed = min(edge.value, outedge.value)
G.edge(edge.Src, outedge.Dest).value += minowed
edge.value -= minowed
outedge.value -= minowed
if(edge.value == 0) G.remove(edge)
if(outedge.value == 0) G.remove(outedge)
stop = false
}
}
}while(!stop)
This amounts to basically removing any cycles from a graph to making it a DAG
.