Recherche du flux maximal Ford-Fulkerson programation Java + Algorithme
Recherche
du flux maximal dans un réseau de transport par la méthode de Ford-Fulkerson ( programmation java + code source )
but:
Le but est de
créer un logiciel appliquant un algorithme de flot maximum.
L’algorithme
devant être appliquée est l’algorithme de Ford-Fulkerson.
On comprendra
donc facilement que le langage qui a été choisi pour
coder est le
Java. Les performances du logiciel ne sont pas le but premier
du projet, mais
plutôt son ergonomie et son aspect pédagogique.
|
(I) Marquer
l'entrée s par *.
(II) Soit i un sommet marqué non examiné.
Considérer tous les successeurs j de i :
(III) Si p est marqué, aller en (IV)
S'il reste des sommets marqués non examinés, aller en (II).
Sinon le
flot est optimal, FIN.
(IV) Améliorer
le flot à l'aide de la chaîne améliorante ayant permis
de marquer p
Effacer les
marques, sauf celle de s, et aller en
(I).
Corollaires et théorèmes :
Théorème de
Ford – Fulkerson : La capacité
minimale d'une coupe
est égale au flot maximal.
Corollaire 1 : Une C.N.S pour qu'un flot soit maximal est qu'il
n'existe pas de chaîne
améliorante.
Corollaire 2 : L'algorithme de Ford-Fulkerson construit un flot maximal.
Algorithme de Ford-Fulkerson(1956)
Entrées: G = (X,U) un graphe.
Sorties: Flot maximal.
Début
Initialisation par un
flot initial réalisable (φ = 0)
Tant que le flot n'est pas maximal
Marquage de la
source S
Tant qu'on
marque des sommets
Pour tout
sommet marqué i
Marquer
les sommets j non marqués tq
φ (i ; j) < c(i ; j) ou φ(j ; i ) > 0
Fin pour
Fin Tant que
Si la sortie E
n'est pas marquée alors le flot est
Maximal
Sinon
amélioration du flot
Fin Tant que
Fin
Remarque :
CODE JAVA :
class
ford_fulkerson{
static //Les capacités des arcs
Graphe gr;
int Capacité[][];
//le Flux initial
int Flux[][];
//matrice pour nous aider
(noeud visite)
int aide[][];
//la Chaine ameliorante
int chaine[];
static int j = 0;
static boolean existence_de_la_chaine =
true;
public static void Ford_Fulkerson(int[][]C,
int[][] F, int[] ch, int[][] aide){
System.out.println("Capacité: ");
affichrer_matrice(C);
System.out.println("Flux
: ");
affichrer_matrice(F);
System.out.println();
while(existence_de_la_chaine
== true){ //une chaine ameliorante
existe
chaine(C,ch,aide); //rechercher une chaine a ameliore
if (existence_de_la_chaine == true)
System.out.println("il existe
une chaine a améliorer ");
else
System.out.println("il
n'existe pas une chaine a améliorer
");
if (existence_de_la_chaine == true)
{ System.out.println("la
chaine a améliorer est : ");
affichage(ch);}
System.out.println();
if (existence_de_la_chaine ==
false){int ff=0;
for(int k = 0; k < ch.length; k++){
ff
=ff+F[k][ch.length-1];
}
System.out.println("le
Flot maximum est = "+ff);
}
else{
augmentation_du_flux(C,F,ch); //augmentation du flux
for(int k = 0; k < ch.length; k++){
ch[k] = 0;
}
for(int x = 0; x < aide.length; x++){
for(int y = 0; y <
aide.length;y++){
aide[x][y]=0;
}
}
System.out.println("Flux
aprés l'amélioration :");
affichrer_matrice(F);
}
}
}
//augmentation du flux
public static void
augmentation_du_flux(int[][] C, int[][] F, int[] ch){
int min = minimum(C,ch); //trouver le flux minimum a ajouter
System.out.println("le minimum a
ajouter dans la chaine est: "+min);
int c = 0;
while(ch[c] != (ch.length-1)){
int d = c+1;
C[ch[c]][ch[d]] -= min;
C[ch[d]][ch[c]] += min;
F[ch[c]][ch[d]] += min;
//modification du flux
F[ch[d]][ch[c]] = -F[ch[c]][ch[c+1]];
c++;
}
}
// Méthode pour trouver le flux minimal
// en tenant compte de la chaine a
ameliore
public static int minimum(int[][]C, int[]
ch){
int c=0;
int hhh = 0;
int min = 1000000;
while(ch[c] != (ch.length-1)){
hhh = C[ch[c]][ch[c+1]];
if (hhh < min){
min = hhh;
}
c++;
}
return min;
}
// Méthode pour trouver une chaine
ameliorente
public static void chaine(int[][] C,
int[] ch, int[][] aide){
int c = 0;
int j = 1;
existence_de_la_chaine = false;
int compteur = 0;
while(valider(C[c],ch,aide,c) != -1
&& compteur == 0 ){//Bien qu'il y ait un noeud
ch[j] =
valider(C[c],ch,aide,c);
//valider
if (ch[j] == (ch.length-1)){ // si
on arrive a la sortie
compteur
= 1;
existence_de_la_chaine = true;
}
else{
c = ch[j];
}
j++;
}
if(possible(C[0],aide) == -1 ||
existence_de_la_chaine == true){
//si existe un arc passant par un noeud déja
compter dans la chaine
}
else if(!rechercher((ch.length-1),ch)){ //s'il existe une chaine
j--;
aide[ch[j-1]][ch[j]] = 1;
for(int k = 0; k < ch.length;
k++){
ch[k] = 0;
}
chaine(C,ch,aide);
}
}
// Méthode pour déterminer si un nœud
est valide en fonction
// en se basant sur la matrice
// de nœuds déjà visités ( aide)
public static int valider(int[] r, int[]
cam,int[][] aide,int i){//Arc, chaine, matrice
int c = 0;
while(rechercher(c,cam) || aide[i][c]
== 1){
c = suivant(r,c);
if (c == -1){
return -1;
}
}
return c;
}
// Méthode pour déterminer si un nœud
est deja visité
public static int possible(int[] r, int[][]
aide){
int c = 0;
while(r[c] == 0 || aide[0][c] == 1){
c = suivant(r,c);
if(c == -1){
return -1;
}
}
return c;
}
// Méthode pour obtenir le nœud suivant
(ne pas visite par la chaine)
public static int suivant(int[] r, int
j){
j++;
while(j < r.length){
if(r[j] != 0){
return j;
}
else{
j++;
}
}
return -1;
}
// Méthode pour trouver un nœud dans la chaine
public static boolean rechercher(int j,
int[] ch){
for(int k = 0;k < ch.length;k++){
if(ch[k] == j)
return true;
}
return false;
}
// Méthode pour afficher la matrice
public static void affichrer_matrice(int
[][]a){
System.out.print("\t"+a[i][j]+"\t");
}
System.out.println();
}
System.out.println();
}
//methode pour afficher une
chaine
public static void affichage(int []a){
System.out.print(+a[j]);
if(a[j]==a.length-1)
break;
System.out.print("
---------->");
}
System.out.println();
}
public static void main(String []args){
String typeGr = "Value"; //scan.next();
Graphe gr = new Graphe();
gr.constrGraphe(typeGr);
int Capacité[][] =gr.getmatAdja();
int Flux[][]= new
int[gr.getNbrSom()][gr.getNbrSom()];
int aide[][]=new
int[gr.getNbrSom()][gr.getNbrSom()];
int chaine[] = new int[gr.getNbrSom()];
//l'application de l'algorithme
*/
Ford_Fulkerson(Capacité,Flux,chaine,aide);
}
}
On
retrouve après la matrice
Exemple
Apres
avoir entrer les valeurs des capacités des arcs on retrouve :
Capacité:
0 30 0 0 0 0 0
0 0 10 15 0 0 0
0 0 0 0 16 0 0
0 0 4 0 0 10 0
0 0 0 0 0 10 8
0 0 0 0 6 0 20
0 0 0 0 0 0 0
Flux :
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0
il existe une
chaine a améliorer
la chaine a
améliorer est :
0
---------->1 ---------->2 ---------->4 ---------->5 ---------->6
le minimum a
ajouter dans la chaine est: 10
Flux aprés
l'amélioration :
0 10 0 0 0 0 0
-10 0 10 0 0 0 0
0 -10 0 0 10 0 0
0 0 0 0 0 0 0
0 0 -10 0 0 10 0
0 0 0 0 -10 0 10
0 0 0 0 0 -10 0
il existe une
chaine a améliorer
la chaine a
améliorer est :
0
---------->1 ---------->3 ---------->2 ---------->4 ---------->6
le minimum a
ajouter dans la chaine est: 4
Flux aprés
l'amélioration :
0 14 0 0 0 0 0
-14 0 10 4 0 0 0
0 -10 0 -4 14 0 0
0 -4 4 0 0 0 0
0 0 -14 0 0 10 4
0 0 0 0 -10 0 10
0 0 0 0 -4 -10 0
il existe une
chaine a améliorer
la chaine a
améliorer est :
0
---------->1 ---------->3 ---------->5 ---------->4 ---------->6
le minimum a
ajouter dans la chaine est: 4
Flux aprés
l'amélioration :
0 18 0 0 0 0 0
-18 0 10 8 0 0 0
0 -10 0 -4 14 0 0
0 -8 4 0 0 4 0
0 0 -14 0 0 6 8
0 0 0 -4 -6 0 10
0 0 0 0 -8 -10 0
il existe une
chaine a améliorer
la chaine a
améliorer est :
0
---------->1 ---------->3 ---------->5 ---------->6
le minimum a
ajouter dans la chaine est: 6
Flux aprés
l'amélioration :
0 24 0 0 0 0 0
-24 0 10 14 0 0 0
0 -10 0 -4 14 0 0
0 -14 4 0 0 10 0
0 0 -14 0 0 6 8
0 0 0 -10 -6 0 16
0 0 0 0 -8 -16 0
il n'existe pas
une chaine a améliorer
le Flot maximum
est = 24
Conclusion :
Le bilan est que nous avons atteint les
objectifs fixés en début de projet.
Pour conclure, on peut dire que ce projet a
été particulièrement intéressant.
D’un point de vue pédagogique, le fait de
devoir créer un logiciel pédagogique nous a permis de comprendre encore mieux
le fonctionnement de l’algorithme de flot
maximum.