FORD FULKERSON EN C

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define m 10
#define infini 100
//creation d'un graphe des seccu
void creation(int n,int g[m][m])
{
int i,j;
for(i=0;i<n;i++)

{
j=-1;
do
{
j++;
printf("donner les successeurs de sommet %d\n",i);
scanf("%d",&g[i][j]);
}
while(g[i][j]!=-1);
} }
// afichage_de_graphe
void afichage_de_graphe(int n,int g[m][m])
{
int i,j;
for(i=0;i<n;i++)
{
printf("%d|\t",i);
for(j=0;g[i][j]!=-1;j++)
{
printf("%d\t",g[i][j]);
}
printf("\n");
} }

// creation d'une graphe valueé
void creation_g_v(int n,int g[m][m],int v[m][m])
{
int i,j,s;

for(i=0;i<n;i++)
{for(j=0;j<n;j++)
v[i][j]=0;
}
for(i=0;i<n;i++)
{
j=0;
while(g[i][j]!=-1)
{
printf("saisir le cout d'arct %d -------> %d : ",i,g[i][j]);
scanf("%d",&v[i][g[i][j]]);
j++;
}
}
}
// afficher_v
void afficher_v(int n,int t[m][m])
{ int i,j;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("%d\t",t[i][j]);
}
printf("\n");
} }
//L'affichage d'un tableau
void afficher_tab(int n,int t[10])
{
int i;
for(i=0;i<n;i++)
{
printf("%d\t",t[i]);
}
printf("\n");
}
//chercher un chemin dans un graphe
void chercher_chemin(int i,int f,int n,int G[m][m])
{
int pere[m],pile[m],j,u,k,v,compt=0;
for(k=0;k<n;k++)
pere[k]=-1;
pile[compt]=i;
compt++;
while(compt!=0&&pile[compt-1]!=f)
{
u=pile[compt-1];
j=0;
v=G[u][j];
while(v!=-1&&pere[v]!=-1)
{
j++;
v=G[u][j];
}
if(v!=-1)
{
pere[v]=u;
pile[compt]=v;
compt++;
}
else
compt--;
}
if(compt==0)
printf("il n'exise pas de chemin\n");
else
{
printf("le chemin est:\n");
fflush(stdin);
afficher_tab(compt,pile);
}
}
/*************************** dantzig ****************************/
void dantzig(int i1,int f,int n,int g[m][m],int l[m][m])
{
int j,t,k,v,c,ok,ok1,z,q;
//y[]:sont les sommets qui peut etre marque dans A
int y[m],min,min1;
int a[m],b[m],p[m],i; //vecteur a[] signifie les sommets qui marquer dans A (ie) Yj
int l_ampda[m],l_ampda1[m];
int M[m][m],G1[m][m];
for(i=0;i<n;i++)
{ a[i]=-1;
p[i]=-1;
}
/*dans l'etape 1er on pose l_ampda1[0]=0;et a[0]=0
t.que les sommets X1=0,X2=2,...Xi=i.... Xn=n-1*/
a[0]=i1; p[i1]=0;k=0;
l_ampda1[i1]=0;
while(a[k]!=f&&k<n)
{ printf("%d eme iteration\n",k);
/* à la K éme iteration on ait definie la fonction l_ampda1 un ensemble Ak={X1,X2,...Xk]
on associe à chaque sommet Xj appartient Ak un sommet Yjn'appartient pas à Ak
et tel que (Xj,Yj) appartient à U et tel que la longueur l[xj][yj] soit minimun*/
t=0;k++;c=0;
while(t<k)
{ok=0;ok1=0;
min=infini;
for(j=0;g[a[t]][j]!=-1;j++)
{if(p[g[a[t]][j]]!=-1)
{ ok=1;}
else
{
if(min>l[a[t]][g[a[t]][j]])
{
min=l[a[t]][g[a[t]][j]];

l_ampda[t]=l_ampda1[a[t]]+min;
y[t]=g[a[t]][j];ok=1;ok1=1;b[c]=t;
} }

} if(ok1==1)
{
printf("les sommets qui peut marqued'apres la sommet %d est: %d\n",a[t],y[b[c]]);
c++;
}
if(ok==1)t++;
}
/* dans la 3éme etape on cherche le sommet Xq appartient à Ak tel que
l_ampda1[Xq]+l[Xq][Yq]=min(l_ampda1[Xj]+l[Xj][Yj])
on pose alors Ak+1=AkU{Yq} et l_ampda1[Yq]=l_ampda1[Xq]+l[Xq][Yq]
puis on revient à l'etape 2 jusqu'à atteindre Xn */

min1=infini;
for(i=0;i<c;i++)
{
if(min1>=l_ampda[b[i]])
{ min1=l_ampda[b[i]];
v=y[b[i]];
z=a[b[i]];

} }
M[z][v]=1;
p[v]=0;
a[k]=v;
l_ampda1[v]=min1;
printf("sommet qui marque d'apres la sommet preduscusseur %d est:%d\n",z,a[k]);
printf("l_ampda est:%d\n",l_ampda1[v]);
}

if(a[k]==n-1)
{

for(j=0;j<n;j++)
{q=0;
for(i=0;i<n;i++)
{
if(M[j][i]==1)
{
G1[j][q]=i;
q++;
}
}
G1[j][q]=-1;
}
chercher_chemin(i1,f,n,G1);
printf("la valeur de chemin minimal allant de X1=%d à Xn=%d est:%d\t",i1,f,l_ampda1[v]);
}
else
printf("n existe pas allant de X1=0 à Xn=n-1" );
}


/****************** main *************************/
main()
{
printf("=========================================================\n\n");
printf(" UNIVERSITE SIDI MOHAMED BEN ABDELLAH \n\n");
printf(" FACULTE DES SCIENCES ET TECHNIQUES FES \n");
printf(" DEPARTEMENT MATHEMATIQUE \n");
printf(" LICENCE DE CALCULE SCIENTIFIQUE ET LES APPLICATION \n");
printf(" ETUDIANT : TAREK KAOUNI \n");
printf(" MODULE DE RECHERCHE OPERATIONNELLE \n");
printf("===========================================================\n");
printf(" ***bonjour*** \n\n");
printf(" 15-04-2009 \n\n");
printf("===========================================================\n\n\n\n");
int n,i,f;
int g[m][m];
int v[m][m];
printf("introduire le nombre de sommet n :");
scanf("%d",&n);
printf("\n Attention! numerote les sommets du graphe dans un ordre quelconque \n");
printf("tel que les numerotation entre 0 et %d\n\n\n",n-1);
getch();
creation(n,g);
getch();
afichage_de_graphe(n,g);
getch();
creation_g_v(n,g,v);
afficher_v(n,v);
printf("saisir l extrimiter initial de chemin : ");
scanf("%d",&i);
do{
printf("saisir l extrimiter final de chemin : ");
scanf("%d",&f);
}while(f<i);
printf(" Algorithme de DANTZIG :\n\n\n");
dantzig(i,f,n,g,v);
system("pause");
return 0;
}

salut
moi aussi j'aimerai bien avoir l'implémentation en language C de l'algorithme de ford Fulkerson,je vous remercie d'avance.

j'aimerai bien avoir une explication de l'algorithme de ford fulkerson (les document sur le net sont trop compliqué)
merci

salut tout le monde ben j voudrais aussi avoir de l'aide concernant la méthode de ford-fulkerson en langage C si c'est possible car il s'agit ici de la méthode de DANTZIG ce qui est totalement différent


merci d'avance