El problema

Recientemente se me pidió que calculara el dinero adeudado entre un grupo de personas que viajaron juntas en un viaje y se encontró con un problema interesante: dado que usted sabe las cantidades que cada persona le debe a otra, ¿qué es un algoritmo general para consolidar las deudas entre las personas? ¿De modo que solo es necesario realizar el número mínimo de pagos? Toma esto como un ejemplo:

Mike le debe a John 100John le debe a Rachel 200Mike le debe a Rachel 400

Podemos eliminar un pago entre Mike y John reformulando las deudas de esta manera:

Mike le debe a John 0John le debe a Rachel 100Mike le debe a Rachel 500

Hice los cálculos a mano ya que era bastante fácil, pero luego el programador en mí estaba ansioso por encontrar un algoritmo general para hacerlo en un grupo arbitrariamente grande. Esto me parece un algoritmo de gráfico, así que lo reformularé como un gráfico:

Visto como un gráficoLos vértices son las personas del grupo.Los bordes están dirigidos y ponderados por la cantidad adeudada. Por ejemplo, una ventaja de Mike a Rachel con un peso 500 significa que Mike le debe a Rachel 500.Restricción: la suma neta de pesos para cada nodo debe permanecer sin cambios.El objetivo es encontrar un gráfico con el número mínimo de bordes que aún cumplan con la restricción.