Début de l'algorithme de Ford-Fulkerson

[Inpu]

Bonjour,

J'essaye de comprendre l'algorithme de Ford Fulkerson, en particulier comment le "commencer", je m'explique :

On part à la base d'un graphe avec des capacités, si je comprend bien on doit au début commencer par :

- Faire passer un flot au jugé, (soit de valeur 0, soit des valeurs respectant la loi de kirchhoff).
- Procéder aux marquages, faire les calculs, etc... (cette partie je l'ai comprise).

Je ne comprend pas le principe de faire passer le "flot au jugé". Si par exemple je sature tout les arcs partant de la source, tout en respectant la loi de kirchhoff, comment puis-je faire pour procéder au marquage ? Il y a t'il une règle à suivre pour faire passer un flot au jugé ?

Merci, et bonne journée !

[Ben314]

Salut,
Si en cherchant un flot "au jugé", tu trouve un truc qui sature tout les arcs partant de la source (ou tout ceux arrrivant au but), ben je crois bien que c'est pas trop la peine de chercher à l'améliorer :zen:

Et sinon, ton flot "au jugé", tu peut partir de 0 partout et tu "l'augmenter" temps que le graphe formé des arrêtes non saturées permet encore de trouver des chemins allant de la source au but (donc ce que tu trouve est un espèce de "maximum local au problème de départ)
Tu applique ensuite l'algo de Ford-Fulkerson pour voir s'il y a moyen d'augmenter ce max local en parcourant certaines arrêtes "à rebrousse poil".

[Inpu]

Merci, c'est plus clair maintenant ! :)

[Ben314]

Aprés, tu peut aussi dés le départ (i.e. avec des flux nuls partout) appliquer l'algo de Ford-Fulkerson : vu que les flux sont nuls, il ne peut pas prendre les arrêtes "à rebrousse poil" et il commencer par ne chercher que des chemins allant de la source au but en passant par des arrêtes non saturées.

Tu y gagne en programmation (une seule boucle à faire), mais je me demande si tu y perd pas un peu en temps (en moyenne), mais en fait, j'en sait rien...

[Dlzlogic]

Bonjour,
Je suis d'accord avec Ben. En informatique, on appelle ça l'initialisation.
Si je recherche une valeur maximale dans une liste, je vais initialiser la valeur de départ, à un nombre très petit, 0 si il n'y a que des valeurs positives, un grand nombre négatif dans le cas contraire.