Ford Fulkerson Flot maximal en langage C

[saad17453]

Bonjour tout le monde
j'aissaye depuis 2 jours de programmer l'algorithme de ford fulkerson sur C mais sans resultats
voici l'algorithme:
https://space.zeo.net/z/ui0z
Merci pour votre aide
-----

[saad17453]

personne n'a une idée ?

[Optimix]

Je possède un code de décision en flot optimal (modèle de Ford Fulkerson) qui fonctionne très bien. Mais il est écrit dans un Basic des toutes premières heures de la micro (début des années 80). Il est donc très facile à lire comme tout ce qui a été écrit pour Amstrad, Commodore 64, Thomson, Atari, etc. à une époque où la recherche opérationnelle s'imposait.
Comme je tiens à ne pas mettre sur la place publique un source qui n'est pas de moi, je suis tout disposé à vous l'envoyer en MP, parce qu'il vous serait très difficile aujourd'hui de trouver les bouquins de Jean-Pierre Blanger (éditions du P.S.I.). Pas le temps, en ce moment, de tester votre algo. A vous de décider en fonction de ce que vous savez de ce modèle.

[whoami]

Bonjour,

Tu prétends vouloir programmer un algorithme en C, et le lien que tu donnes renvoie cet algorithme implémenté en C ...

... je ne comprends donc pas ton problème.

Sinon, pour implémenter un algorithme, on commence par l'étudier, jusqu'à l'avoir bien compris. La suite est alors de la pure routine du moment qu'on connaît le langage de destination.

[A voir en vidéo sur Futura]

[acx01b]

c'est quel algorithme précisément que tu veux implémenter ? (donne le lien vers le cours qui le décrit)
parce qu'en regardant vite fait sur wikipedia anglais, je ne reconnais pas celui que j'ai appris, et en plus ils se contredisent d'un paragraphe à l'autre.

surtout quand ils donnent un exemple qui ne converge pas, ça m'étonne car il me semblait que celui que j'avais appris convergeait toujours vers le flot max

[saad17453]

Voici l'algortihme

a) on demmare d'un flot compatible
b) on marque le sommet d'entrée E
soit (i,j) un arc , si i est marqué et j n'est pas marqué on marque j si :
-(i,j) un arc et f<c
-(j,i) un arc et f>0
c) si on n'arrive pas à marquer la sortie S alors le flot est maximal sinon on passe à l'étape d)
d) soit f'=f+alpha
avec alpha=min(alpha 1, alpha 2)
alpha 1=min(c - f)
alpha 2 = min(f)
puis en revient à b)
f est le flot de l'arc (i,j)
c sa capacité.
Merci

[acx01b]

graphe orienté : l'arrête (i,j) n'est pas (j,i)

c'est un peu n'importe quoi ton étape d) et aussi ton étape b)

f(i,j) : flot de i à j
c(i,j) : capacité de l'arc (i,j)
flot compatible : 0 <= f(i,j) <= c(i,j)

b') on ajoute au graphe G' des sommets marqués des arcs :
de valeur v(i,j) = c(i,j) - f(i,j) + f(j,i), si v(i,j) < 0 on vire l'arc


d) on trouve un chemin (E=0,a_1...,a_N=S) dans ce nouveau graphe,

on trouve de combien on peut augmenter le flot sur ce chemin V = min des v(a_n,a_{n+1}
et on augmente le flot d'autant sur ce chemin :
de préférence f(i,j) += V
et si besoin (capacité atteinte) : f(i,j) = c et f(j,i) -= c - V

d') rien n'interdit de garder le même graphe G', en actualisant les v(i,j)
et de reprendre b) jusqu'à qu'il n'y ait plus de chemin de E à S

question : quand G' n'a plus de chemin de E à S, c'est terminé ou non ?
réponse : non il faut reprendre à b)

[acx01b]

je voulais dire si v(i,j) = 0 on vire l'arc

on a donc que souvent deux sommets sont connectés par le même arc

les chemins avec boucle sont acceptables (quel intérêt ?) si on ne passe pas 2 fois par la même arrête