Le temps de la complexité de la Ford-Fulkerson méthode dans un réseau de flux avec la capacité de l'unité bords

O(M*f) est connu à l'exécution d'estimation de temps pour Ford-Fulkerson sur des graphes avec entier capacités, où M est le nombre d'arêtes et f la valeur maximale de débit, juste parce que c'est facile à trouver en augmentant les chemins d'accès dans O(M) chaque, et chaque chemin d'accès augmente le débit d'au moins 1.

Si votre graphique n'a pas de dupliquer les bords (qui est, il n'y a pas de paire de bords qui a le même début et de fin de sommets), et chaque arête a capacité de l'unité, puis le maximum de flux de f est rien de plus que le nombre de sommets N (juste parce qu'il n'y est pas plus de N-1 bords en allant de la source), et donc de la complexité est en effet O(N*M).

Toutefois, si votre graphique est autorisé à avoir de doublons de bords (mais encore chaque arête a une capacité de 1), alors f peut être plus grand que N, et jusqu'à M, et la complexité du temps peut devenir O(M*M), et il n'est pas difficile à venir avec un exemple où une telle complexité a lieu.