O problema

Recentemente me pediram para calcular o dinheiro devido entre um grupo de pessoas que viajaram juntas e se depararam com um problema interessante: dado que você sabe os valores que cada pessoa deve a outro, o que é um algoritmo geral para consolidar as dívidas entre as pessoas? de modo que apenas o número mínimo de pagamentos precisa ser feito? Tome isso como um exemplo:

Mike deve John 100João deve Rachel 200Mike deve Rachel 400

Podemos remover um pagamento entre Mike e John reformulando as dívidas assim:

Mike deve John 0João deve Rachel 100Mike deve Rachel 500

Eu fiz a matemática com a mão desde que foi bastante fácil, mas o programador em mim estava ansioso para descobrir um algoritmo geral para fazer isso para um grupo arbitrariamente grande. Isso parece um algoritmo de gráfico para mim, então vou reformular isso como um gráfico:

Visto como um gráficoOs vértices são as pessoas do grupoAs bordas são direcionadas e ponderadas pelo valor devido. Por exemplo, uma vantagem de Mike para Rachel com peso 500 significa que Mike deve Rachel 500.Restrição: a soma líquida de pesos para cada nó deve permanecer inalterada.O objetivo é encontrar um gráfico com o número mínimo de arestas que ainda satisfaçam a restrição.