Bonjour,

J'ai un probleme pour lequel je n'arrive pas à trouver d'algorithme standard, mais je suppose qu'il doit en exister un :

Si on a un graph du genre a->b->c, 'a' est l'entrée et 'b' la sortie. Si la capacité maximal du premier arc est 2 mais que la capacité maximale du second est 1, tout chemin de a vers c ne pourra emprunter qu'une seule fois le premier arc (meme si sa capacité est 2). Je cherche donc a calculer "l'empruntabilité" maximale des arcs. Je travail sur des 1 graphes connexes, qui peuvent comprendre des cycles ou des cycles imbriqués.

Quelqun peut-il me dire s'il existe un algorithme connu pour ce probleme ? Au niveau performances, mes graphes auront rarement plus de 100 sommets (300 grand maximum), et 5 ou 10 secondes de calcul sont acceptables.

Merci,
John.