Imaginez un voyage avec 10 amis. En une semaine, ils créent 50 dépenses partagées : Alice paie le dîner, Bob l’Uber, Charlie les boissons, etc. À la fin, si chacun rembourse exactement chaque transaction, il faut des dizaines de virements.
C’est inefficace, confus et cela crée des frais inutiles. Chez Finovoo, l’objectif est de réduire ce chaos au minimum absolu de virements nécessaires grâce à la théorie des graphes.
Le problème N²
Dans une approche naïve, le nombre de transactions potentielles croît quadratiquement avec le nombre de participants. Si chacun doit de l’argent à chacun, un groupe de 10 personnes peut théoriquement nécessiter 90 transactions.
Visualiser les dettes sous forme de graphe
Nous modélisons les finances du groupe comme un graphe orienté : les participants sont des nœuds, les dettes des arêtes orientées. Une arête de A vers B avec un poids de 20 $ signifie que A doit 20 $ à B.
Étape 1 : calculer les soldes nets
La première étape consiste à ignorer les transactions individuelles et à calculer le solde net de chaque personne. Peu importe qu’Alice doive 10 $ à Bob et Bob 5 $ à Alice : le résultat net est qu’Alice doit 5 $.
Exemple : Alice (+50), Bob (-20), Charlie (-30). Alice doit recevoir 50 $, tandis que Bob et Charlie doivent payer. L’historique précis importe moins que l’équilibrage des soldes.
Étape 2 : l’algorithme glouton de mise en correspondance
Une fois les soldes nets connus, nous reconstruisons un graphe avec le moins d’arêtes possible. Nous utilisons un algorithme glouton pour associer débiteurs et créanciers.
- Séparer les participants en deux listes : débiteurs (solde négatif) et créanciers (solde positif).
- Prendre le plus grand débiteur et le plus grand créancier.
- Les associer. Si le débiteur doit 100 $ et le créancier doit recevoir 80 $, le débiteur paie 80 $. Le créancier est réglé et le débiteur reste à -20 $.
- Répéter avec les soldes restants jusqu’à ce que tout le monde soit à zéro.
Gérer les cycles
L’une des parties les plus élégantes de la simplification consiste à supprimer les cycles : A doit à B, B doit à C, et C doit à A.
Si le flux est égal, par exemple 10 $ chacun en cercle, l’effet net est nul. Le calcul des soldes nets élimine naturellement ces cycles avant même la phase de règlement.
Contraintes du monde réel
Les mathématiques sont élégantes, mais le réel est plus complexe. Certains utilisateurs demandent parfois de ne pas simplifier entre certaines personnes. Nous découpons alors le graphe en sous-graphes et optimisons localement.
En réduisant le nombre d’arêtes, nous faisons gagner du temps, des frais de transfert et évitons le suivi de dizaines de petits paiements.