language agnostic - algorithm to determine minimum payments amongst a group

Question

The Problem

I was recently asked to calculate the money owed amongst a group of people who went on a trip together and came upon an interesting problem: given that you know the amounts that each person owes another, what is a general algorithm to consolidate the debts between people so that only the minimum number of payments needs to be made? Take this as an example:

• Mike owes John 100
• John owes Rachel 200
• Mike owes Rachel 400

We can remove a payment between Mike and John by reformulating the debts like this:

• Mike owes John 0
• John owes Rachel 100
• Mike owes Rachel 500

I did the math by hand since it was easy enough, but then the programmer in me was itching to figure out a general algorithm to do it for an arbitrarily large group. This seems like a graph algorithm to me, so I'll reformulate this as a graph:

Viewed as a Graph

• The vertices are the people in the group
• The edges are directed and weighted by the amount owed. For example, an edge from Mike to Rachel with weight 500 means that Mike owes Rachel 500.
• Constraint: the net sum of weights for each node must remain unchanged.
• The goal is to find a graph with the minimum number of edges that still satisfy the constraint.

Answer 1

My opinion: You're making this overly complicated.

Think of it as a "pool" of money, and lose the relationships altogether:

Instead of:

• Mike owes John 100
• John owes Rachel 200
• Mike owes Rachel 400

The algorithm only has to think:

• Mike owes 100
• John is owed 100
• John owes 200
• Rachel is owed 200
• Mike owes 400
• Rachel is owed 400

Netting this:

• Mike owes 500
• John owes 100
• Rachel is owed 600

Separate this into a list of "givers" and "receivers". Each giver on the list will go through the list of receivers, giving each receiver what they need until the giver has payed up. When a receiver receives everything they need, they go off the list.

Later Edit

As other posters have observed, this simplifies the problem. However, there might be an optimal ordering of the "givers" and "receivers" lists, but we haven't yet identified a straightforward way to determine this ordering.