Bonsoir,
J'ai essayé de coder, en C, l'algorithme de Ford-Fulkerson, qui permet de calculer le flot maximal entre 2 sommets d'un graphe. J'ai obtenu un résultat, mais je n'ai aucune garantie que ce résultat est juste ; et comme, dans mon cas, le graphe contient énormément de sommets et d'arcs, c'est impossible (ou presque) de le vérifier "à la main". J'aimerais donc savoir s'il existerait des logiciels permettant de calculer cela automatiquement. Si oui, qqn pourrait-il m'en citer, afin que je puisse l'utiliser pour vérifier que mon programme est correct ?
Merci d'avance.

Salut
Le meme algorithme utilisé sur un graphe plus petit que tu aura corrigé a la main?

L'algorithme de flot maximum se résoud par programmation linéaire . Par conséquent si tu ajoutes au modèle des contraintes ; c'est à dire celles fournies par ton résultat (le flot exacte trouvé sur chaque arête), tu verras si le système linéaire est réalisable. Si oui, ton résultat est juste mais peut être sous optimal ...; si non, ton résultat est faux, ca c'est sûr.
Au niveau de la résolution du problème par programmation linéaire, tu n'as que 2 contraintes ! c'est donc vite testé :  
 
1ere contrainte : assurer l'émission du flot depuis le noeud source (autrement dit tout ce qui arrive moins tout ce qui en sort est egal à la demande (mais en valeur negative))
2ème contrainte : tout les noeuds du graphe (sauf la source et la destination) VEHICULENT le flot, c'est à dire qu'ils doivent conserver le flot : pour chacun de ces noeuds, tout ce qui rentre - tout ce qui sort est NUL.
 
Voilà .
 
RQ : et même avec ces deux contraintes, tu pourrais vérifier à la main...en vérifiant en plus que tout ce rentre - tout ce qui sort du noeud destination est egal à ce qui est émis de la source.