FORD FULKERSON EN C
Fermé
hamidou1631
Messages postés
9
Date d'inscription
vendredi 2 février 2007
Statut
Membre
Dernière intervention
19 septembre 2009
-
13 mars 2007 à 15:04
periplasme Messages postés 391 Date d'inscription vendredi 22 avril 2011 Statut Membre Dernière intervention 5 février 2013 - 9 juil. 2011 à 13:43
periplasme Messages postés 391 Date d'inscription vendredi 22 avril 2011 Statut Membre Dernière intervention 5 février 2013 - 9 juil. 2011 à 13:43
5 réponses
#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;
}
#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.
moi aussi j'aimerai bien avoir l'implémentation en language C de l'algorithme de ford Fulkerson,je vous remercie d'avance.
NEOEVEN
Messages postés
4
Date d'inscription
mardi 13 mars 2007
Statut
Membre
Dernière intervention
13 mars 2007
1
13 mars 2007 à 15:06
13 mars 2007 à 15:06
http://students.odl.qmul.ac.uk/aduni/05_algorithms/handouts/Reciation_09.html#25630
j'aimerai bien avoir une explication de l'algorithme de ford fulkerson (les document sur le net sont trop compliqué)
merci
merci
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
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
merci d'avance
12 janv. 2010 à 10:50
31 janv. 2011 à 02:38
9 juil. 2011 à 12:39
je sais pas trop comment te contacter. stp fait moi signe a ce mail: kenwear100@yahoo.fr
merci
9 juil. 2011 à 13:29
9 juil. 2011 à 13:37
Effectivement le prototype du main n'est pas valide. Mais ça m'étonnerait qu'il lise ton commentaire vu que ça remonte à 2009 ;-)))