Finding the minimum transaction

Question

Given a list of transactions like:

A -> 10 to B
B -> 10 to C

The naive way to settle the transaction would be:

C owes 10 to B
B owes 10 to A

But the same transaction could be settled by:

C owes 10 to A

I am representing each transaction as an object:

{
  amount: Number,
  account: Object,
  linkId: Object  
}

So, for a transaction like: A gives 10 to B there would be an object like:

{amount: +10, account: B, linkId: A}

So, if I visualize the transactions then each node could have cycles too. I am trying to find an efficient algorithm but I don't feel confident.

Answer 1

This looks like the minimize cash flow problem.

Works like this: total credits and debts of each A,B,C... to get a net values for them. Find the two extremes (max at credit and max at debit) and have them transact. The min of the two will have their net go to zero. Now do it again with the ones left over.

It works but sadly this is O(n²).