Simplify Debt

[mweinelt]

If A owes B and B owes C and C owes A we have a loop, which can be simplified to reduce the amount of physical transactions and total money exchanged between users.

The general idea of an algorithm is:

• Use a weighted, directed graph
• The weight is the sum of debt between the two vertices, which are users
• Find a cycle in the graph
• Find the smallest weight on the cycle
• Subtract the smallest weight from all weights in the cycle

Simplified!

More References:

• https://web.archive.org/web/20170213201610/http://jackiebaek.com/2015/04/09/splitwises-algorithm-to-simplify-debts/
• https://www.quora.com/What-algorithm-or-solution-do-the-people-at-Splitwise-use-for-its-debt-simplification-feature?share=1

[luelista]

I'd love to have this and would definitely integrate it if someone would implement the algorithm in PHP or Javascript. Not sure how quick I'll understand it enough to do it myself... ;-)