How to calculate minimum amount of transactions needed for n friends to clear they debts with each other? Suppose you have n friends, $ a_1, a_2, ... a_n $, such that each of them owes each other an amount of money equal or greather than 0. How to calculate the minimum amount of transactions needed so that all of them get their money back?
Example: 

3 friends, A, B, and C. A owes B \$8, B owes C \$5, and C owes A \$5. The minimum amount of transactions needed would be 1, namely, A should give B \$3.

It can be modeled as a digraph, where each friend is a vertex and $c_e, e = (x,y), $ is the amount of money that friend $x$ owes to $y$. The first step seems to calculate $d* = d_{in} - d_{out}$ for every vertex.
Being $D$ the original digraph, the problem might be seen as finding a digraph $D'$ with the same set of vertices as $D$ such that every vertex has the same $d*$ as $D$ and the set of edges is minimum. But that's not helping me to find an algorithm solution... Any suggestions?
 A: Your first step is good: for each friend $i$, let $d_i$ be the net amount that friend $i$ owes/is owed, i.e. $d_{in} - d_{out}$ for vertex $i$.
We want to determine the minimum number of transactions that will reset all $d_i$ to $0$.

Problem 1. Given a list of integers $d_1, \ldots, d_n$, such that $\sum d_i = 0$, determine the minimum number of transactions $m$ to reset all $d_i$ to $0$.

I claim that $m = n - k$, where $k$ is the maximum number of subsets $k$ to divide $\{d_1, \ldots, d_n\}$ into, such that each subset sums to $0$ on its own. Why is this equivalent?


*

*First suppose $k$ is the maximum number of such subsets. Then, each of those subsets can settle the debts on its own. A set of $a$ people can settle their debts in $a-1$ transactions by just starting from the first person and having them pay or be payed by the second person, and so on. The total number of transactions will be $a - 1$ for each set of people of size $a$, which adds to $n - k$ since there are $k$ sets.

*Now why is $n - k$ the minimum? If it were possible to do it in $m < n - k$ transactions, then that would correspond to $m$ edges in a graph of $n$ vertices, with $m < n - k$. Each connected component of the graph of size $a$ needs to have at least $a - 1$ edges, so there are strictly more than $k$ connected components. Then each connected component is a subset summing to zero, contradicting that $k$ was the maximum number of subsets.
So we have shown that Problem 1 is equivalent (reducible both ways by a trivial reduction) to Problem 2:

Problem 2. Given a list of integers $d_1, \ldots, d_n$, such that $\sum d_i = 0$, determine the maximum number of nonempty subsets $k$ to divide $\{d_1, \ldots, d_n\}$ into, such that each subset sums to $0$.

Problem 2 is NP-hard, so we can't reasonably hope for a good exact algorithm. We can prove it is NP-hard by reduction from SubsetSum.

Reduction from SubsetSum to Problem 2. An instance of SubsetSum consists of positive integers $a_1, a_2, \ldots, a_n$, and a target $T$. The question is whether there exists a subset summing to $T$. Suppose that we can solve Problem 2. Then, on input an instance of SubsetSum, construct a new list of integers $a_1, a_2, \ldots, a_n, -T, T - A$, where $A = \sum_{i=1}^n a_i$. If there is a subset of $a_i$ summing to $T$, then Problem 2 will be solvable with two subsets: the subset of $a_1, a_2, \ldots, a_n$ summing to $T$ together with $-T$, and everything else. So the answer to Problem 2 will be $2$. Otherwise, if there is no subset summing to $T$, then the answer to Problem 2 is $1$, because there is no way to split into two subsets. In particular, the only two elements that aren't positive are $-T$ and $T - A$, and so we would have to have one set containing $-T$ and one containing $T-A$, but then we would have a solution to SubsetSum in the first set.

So I have argued that no truly efficient algorithm will likely exist, but we could still try to come up with a good approximation algorithm, or some algorithm with exponential running time.
By the way, I had some luck in finding related information on this problem by Googling Minimum Transaction Problem and Optimal Account Balancing. This is a StackExchange question identical to your own; the answers either don't give an algorithm, or give one that doesn't guarantee minimum number of payments.
