From 9fe033ea88c2f705ec18c232873d056e0c229d72 Mon Sep 17 00:00:00 2001 From: Gaspard Coulet Date: Wed, 28 Apr 2021 23:05:53 +0200 Subject: Initial commit --- sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1 | Bin 0 -> 27229 bytes sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1.cc | 101 + sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/a.out | Bin 0 -> 18964 bytes sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/ex2arbre.ps | 541 + sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/ex2graphe.ps | 7385 ++++ sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/ex3arbre.ps | 901 + sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/ex3graphe.ps | 20305 +++++++++++ sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/tp2 | Bin 0 -> 18964 bytes sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/tp2.cc | 189 + sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/tribulle.cc | 189 + sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP3/tp3 | Bin 0 -> 64949 bytes sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP3/tp3.cc | 223 + sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP4/affichage.ps | 34569 ++++++++++++++++++ .../TP-DEVOIRTP/TP4/affichagefin.ps | 9009 +++++ sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP4/tp4 | Bin 0 -> 27991 bytes sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP4/tp4.cc | 182 + sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/tp5 | Bin 0 -> 14458 bytes sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/tp5.cc | 243 + sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/tp50 | Bin 0 -> 13497 bytes sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/tp50.cc | 74 + sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/villes.cc | 126 + sem_5/HLIN501_Graphes/TP/TP1/tp1 | Bin 0 -> 27223 bytes sem_5/HLIN501_Graphes/TP/TP1/tp1.cc | 96 + sem_5/HLIN501_Graphes/TP/TP2/a.out | Bin 0 -> 18964 bytes sem_5/HLIN501_Graphes/TP/TP2/arbre.ps | 46 + sem_5/HLIN501_Graphes/TP/TP2/graphe.ps | 70 + sem_5/HLIN501_Graphes/TP/TP2/tp2.cc | 189 + sem_5/HLIN501_Graphes/TP/TP2/tribulle.cc | 189 + sem_5/HLIN501_Graphes/TP/TP3/tp3 | Bin 0 -> 64906 bytes sem_5/HLIN501_Graphes/TP/TP3/tp3.cc | 207 + sem_5/HLIN501_Graphes/TP/TP4/affichage.ps | 34961 +++++++++++++++++++ sem_5/HLIN501_Graphes/TP/TP4/affichagefin.ps | 9009 +++++ sem_5/HLIN501_Graphes/TP/TP4/tp4 | Bin 0 -> 27991 bytes sem_5/HLIN501_Graphes/TP/TP4/tp4.cc | 170 + sem_5/HLIN501_Graphes/TP/TP5/tp5 | Bin 0 -> 14458 bytes sem_5/HLIN501_Graphes/TP/TP5/tp5.cc | 243 + sem_5/HLIN501_Graphes/TP/TP5/tp50 | Bin 0 -> 13497 bytes sem_5/HLIN501_Graphes/TP/TP5/tp50.cc | 74 + sem_5/HLIN501_Graphes/TP/TP5/villes.cc | 126 + 39 files changed, 119417 insertions(+) create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1 create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1.cc create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/a.out create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/ex2arbre.ps create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/ex2graphe.ps create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/ex3arbre.ps create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/ex3graphe.ps create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/tp2 create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/tp2.cc create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP2/tribulle.cc create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP3/tp3 create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP3/tp3.cc create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP4/affichage.ps create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP4/affichagefin.ps create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP4/tp4 create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP4/tp4.cc create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/tp5 create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/tp5.cc create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/tp50 create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/tp50.cc create mode 100644 sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/villes.cc create mode 100644 sem_5/HLIN501_Graphes/TP/TP1/tp1 create mode 100644 sem_5/HLIN501_Graphes/TP/TP1/tp1.cc create mode 100644 sem_5/HLIN501_Graphes/TP/TP2/a.out create mode 100644 sem_5/HLIN501_Graphes/TP/TP2/arbre.ps create mode 100644 sem_5/HLIN501_Graphes/TP/TP2/graphe.ps create mode 100644 sem_5/HLIN501_Graphes/TP/TP2/tp2.cc create mode 100644 sem_5/HLIN501_Graphes/TP/TP2/tribulle.cc create mode 100644 sem_5/HLIN501_Graphes/TP/TP3/tp3 create mode 100644 sem_5/HLIN501_Graphes/TP/TP3/tp3.cc create mode 100644 sem_5/HLIN501_Graphes/TP/TP4/affichage.ps create mode 100644 sem_5/HLIN501_Graphes/TP/TP4/affichagefin.ps create mode 100644 sem_5/HLIN501_Graphes/TP/TP4/tp4 create mode 100644 sem_5/HLIN501_Graphes/TP/TP4/tp4.cc create mode 100644 sem_5/HLIN501_Graphes/TP/TP5/tp5 create mode 100644 sem_5/HLIN501_Graphes/TP/TP5/tp5.cc create mode 100644 sem_5/HLIN501_Graphes/TP/TP5/tp50 create mode 100644 sem_5/HLIN501_Graphes/TP/TP5/tp50.cc create mode 100644 sem_5/HLIN501_Graphes/TP/TP5/villes.cc (limited to 'sem_5/HLIN501_Graphes') diff --git a/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1 b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1 new file mode 100644 index 0000000..d5c434d Binary files /dev/null and b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1 differ diff --git a/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1.cc b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1.cc new file mode 100644 index 0000000..c73ad89 --- /dev/null +++ b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP1/tp1.cc @@ -0,0 +1,101 @@ +#include +#include +#include +#include +using namespace std; + +void ecritureTailles(int n, int m, int comp[]); +void composantes(int n, int m, int edge[][2], int comp[]); +void grapheRandom(int,int, int[][2]); +void printgraphe (int, int, int[][2]); +void ecritureTaillesbis(int n, int m, int comp[]); + +int main(int argc, char ** argv) +{ + int n; // Nombre de sommets. + int m; // Nombre d'aretes. + cout << "Entrer le nombre de sommets:"; + cin >> n; + cout << "Entrer le nombre d'aretes:"; + cin >> m; + int edge[m][2]; // Tableau des aretes. + int comp[n]; // comp[i] est le numero de la composante contenant i. + grapheRandom(n,m,edge); + //printgraphe(n,m,edge); + composantes(n,m,edge,comp); + cout<=1){ + cout<<"Il y a "<< tab[i] << " composantes de taille "<< i+1 << " Sommets, le num de cette comp est : "<< comp[i]< L[n]; + for (int i = 0 ; i < n; i ++) { + comp[i]=i; + taille[i]=1; + L[i].push_back(i); + } + for ( int i = 0 ; i < m; i ++){ + int * x = &comp[edge[i][0]]; + int * y = &comp[edge[i][1]]; + if (*x != *y){ + if (*x>*y){ + int aux = *x; + taille[*y]+=taille[aux]; + for(int j = 0; j < taille[aux]; j ++){ + int tmp = L[aux].back(); + comp[tmp]=*y; + L[*y].push_back(tmp); + L[aux].pop_back(); + } + } + } + } +} + +void printgraphe (int n, int m, int edge[][2]){ + cout< +#include +#include +#include +#include + +typedef struct coord{int abs; int ord;} coord; +void pointRandom(int n, coord point[]); +void distances(int n, int m, coord point[], int edge[][3]); +void tri(int m, int edge[][3]); +void affichageGraphique(int n, int m, coord point[], int arbre[][2], const char * filename); +void kruskal (int n, int edge[][3], int arbre[][2]); +void fusion(int tableau[][3],int deb1,int fin1,int fin2); +void tri_fusion(int tableau[][3],int longueur); +void tri_fusion_bis(int tableau[][3],int deb,int fin); +using namespace std; + +int +main() +{ + int n; //Le nombre de points. + cout << "Entrer le nombre de points: "; + cin >> n; + int m=n*(n-1)/2; // Le nombre de paires de points. + coord point[n]; // Les coordonnees des points dans le plan. + int edge[m][3]; // Les paires de points et le carre de leur longueur. + int arbre[n-1][2]; // Les aretes de l'arbre de Kruskal. + pointRandom(n,point); + distances(n,m,point,edge); + tri_fusion(edge,m); + // for (int i =0; i < m; i ++){ + // cout << "point "<< edge[i][0]<<":"<0) + { + tri_fusion_bis(tableau,0,longueur-1); + } + } +void tri(int m, int edge[][3]){ + for (int i = 0 ; i < m ; i ++){ + for(int j=i+1; j < m; j ++){ + if ( edge[i][2]>edge[j][2]){ + swap(edge[i][0],edge[j][0]); + swap(edge[i][1],edge[j][1]); + swap(edge[i][2],edge[j][2]); + } + } + } +} + +void affichageGraphique(int n, int m, coord point[], int arbre[][2], const char * filename) +// Cree le fichier Exemple.ps qui affiche +// les points et l'arbre de Kruskal. +{ + ofstream output; + output.open(filename,ios::out); + output << "%!PS-Adobe-3.0" << endl; + output << "%%BoundingBox: 0 0 612 792" << endl; + output << endl; + for(int i=0;i +#include +#include +#include +#include + +typedef struct coord{int abs; int ord;} coord; +void pointRandom(int n, coord point[]); +void distances(int n, int m, coord point[], int edge[][3]); +void tri(int m, int edge[][3]); +void affichageGraphique(int n, int m, coord point[], int arbre[][2], const char * filename); +void kruskal (int n, int edge[][3], int arbre[][2]); +void fusion(int tableau[][3],int deb1,int fin1,int fin2); +void tri_fusion(int tableau[][3],int longueur); +void tri_fusion_bis(int tableau[][3],int deb,int fin); +using namespace std; + +int +main() +{ + int n; //Le nombre de points. + cout << "Entrer le nombre de points: "; + cin >> n; + int m=n*(n-1)/2; // Le nombre de paires de points. + coord point[n]; // Les coordonnees des points dans le plan. + int edge[m][3]; // Les paires de points et le carre de leur longueur. + int arbre[n-1][2]; // Les aretes de l'arbre de Kruskal. + pointRandom(n,point); + distances(n,m,point,edge); + tri(m,edge); + for (int i =0; i < m; i ++){ + cout << "point "<< edge[i][0]<<":"<0) + { + tri_fusion_bis(tableau,0,longueur-1); + } + } +void tri(int m, int edge[][3]){ + for (int i = 0 ; i < m ; i ++){ + for(int j=i+1; j < m; j ++){ + if ( edge[i][2]>edge[j][2]){ + swap(edge[i][0],edge[j][0]); + swap(edge[i][1],edge[j][1]); + swap(edge[i][2],edge[j][2]); + } + } + } +} + +void affichageGraphique(int n, int m, coord point[], int arbre[][2], const char * filename) +// Cree le fichier Exemple.ps qui affiche +// les points et l'arbre de Kruskal. +{ + ofstream output; + output.open(filename,ios::out); + output << "%!PS-Adobe-3.0" << endl; + output << "%%BoundingBox: 0 0 612 792" << endl; + output << endl; + for(int i=0;i +#include +#include +#include +#include +#include +#include +#include + +typedef struct coord{int abs; int ord;} coord; +bool search (std::vector vec, int x); +void ecritureNiveaux(int n, int niveau[]); +void voisinsRandom(int n, int m, std::vectorvoisins[]); +void afficheGraph (int n, std::vectorvoisins[]); +void parcoursLargeur(int n, std::vectorvoisins[],int niveau[], int ordre[], int pere[]); +void afficheArbre(int n, int pere[], int ordre[]); +void pacoursProf(int n, int r, std::vector*> voisins, int debut[],int fin[], int pere[], int niveau[]); +void vectortostack(int n,std::vector arch[], std::vector* > young); +void afficheArbrebis(int n, int pere[]); +int sommeniveau(int n, int niveau[]); +using namespace std; + +void voisinsRandom(int n, int m, vectorvoisins[]){ + srand(time(NULL)); + int x=1; int y=0; + for (int i = 0; i < m; i ++){ + do { + x = rand()%n; + y = rand()%n; + while (x==y){ + y = rand()%n; + } + } while (search(voisins[x],y)); + voisins[x].push_back(y); + voisins[y].push_back(x); + } +} +bool search (vector vec, int x){ + int i = 0; + if (vec.size()==0){ + return false; + } + while (vec[i]!=x){ + i ++; + if (i>vec.size()){ + return false; + } + } + return true; +} +int main() { + int n; //Le nombre de points. + int m; // nb aretes + cout << "Entrer le nombre de points: "; + cin >> n; + cout << "Entrer le nombre d'aretes: "; + cin>>m; + if (m > n*(n-1)/2){ + cout<<"Nombre d'aretes trop grand, cap à : "<< n*(n-1)/2< voisins[n]; + int pere[n]; + int pere2[n]; + int ordre[n]; + int niveau[n]; + int niveau2[n]; + int debut[n]; + int fin[n]; + vector* > piledevoisins = vector< stack < int > * >(n); + for (int i =0; i < n; i ++){ + piledevoisins[i]=new stack; + } + // for (int i = 0; i < n ; i ++){ + // piledevoisins[i]=new stack; + // } + voisinsRandom(n,m,voisins); + //afficheGraph(n,voisins); + parcoursLargeur(n,voisins,niveau,ordre,pere); + //afficheArbre(n, pere, ordre); + //ecritureNiveaux(n,niveau); + cout<<"Parcours en largeur OK"<voisins[]){ + for (int i =0; i < n; i ++){ + int j = 0; + cout<<"Sommet "<j){ + cout<< " "<voisins[],int niveau[], int ordre[], int pere[]){ + int dejavu[n]; + for (int i =0; i < n; i ++ ){ + dejavu[i]=0; + niveau[i]=0; + } + int r=0; + dejavu[r]=1; + ordre[r]=1; + pere[r]=r; + niveau[r]=0; + queue AT; + AT.push(r); + int t = 2; + while (!AT.empty()){ + int v = AT.front(); + AT.pop(); + for (int i =0; i < voisins[v].size();i ++){ + int x = voisins[v][i]; + if (!dejavu[x]){ + dejavu[x]=1; + AT.push(x); + ordre[x]=t; + t ++; + pere[x]=v; + niveau[x]=niveau[v]+1; + } + } + } +} +void pacoursProf(int n, int r, vector* > voisins, int debut[],int fin[], int pere[] ,int niveau[]){ + bool dejavu[n]; + for (int i =0; i < n; i ++ ){ + dejavu[i]=false; + niveau[i]=0; + } + dejavu[r]=1; + debut[r]=1; + pere[r]=r; + niveau[r]=0; + stack AT; + AT.push(r); + int t = 2; + while (!AT.empty()){ + int x = AT.top(); + if (voisins[x]->empty()){ + AT.pop(); + fin[x]=t; + t ++; + } + else { + int y = voisins[x]->top(); + voisins[x]->pop(); + if (!dejavu[y]){ + dejavu[y]=true; + AT.push(y); + debut[y]=t; + t++; + pere[y]=x; + niveau[y]=niveau[x]+1; + cout << "Niveau de "< +#include +#include +#include +#include + +using namespace std; + +const int N=10; +const int M=(N*(N-1))/2; + +typedef struct coord{int abs; int ord;} coord; +typedef struct point{int x; int y;} point; + +void pointRandom(int n,coord point[][]); +float distancexy(coord p1,coord p2); +void voisins(int n,int dmax,coord point[][],vector voisin[][],int &m); +void voisins2arete(int n,vectorvoisins[],int arete[][2]); +void affichageGraphique(int n,int m,coord point[][],vector voisins[][],const char * name); +bool existe(int n,int dis[],bool traite[]); +int searchsmallest(int n, int dist[],bool traite[]); +void dijkstra(int n,vector voisin[][],coord point[][],int pere[], int m); +int construireArbre(int n,vector voisin[],int pere[]); + +int main(){ + int n; // Le nombre de points. + cout << "Entrer le nombre de points: "; + cin >> n; + int dmax=50; // La distance jusqu'a laquelle on relie deux points. + coord point[N][N]; // Les coordonnees des points. + vector voisin[N][N]; + vector voisinbis[N]; // Les listes de voisins. + int arbre[N-1][2]; // Les aretes de l'arbre de Dijkstra. + int pere[N]; // La relation de filiation de l'arbre de Dijkstra. + int m; // Le nombre d'aretes + int arete[M][2]; // Les aretes du graphe + pointRandom(n,point); + voisins(n,dmax, point, voisin, m); + const char * filename = "affichage.ps"; + affichageGraphique(n,m,point,voisin,filename); + // cout<<"Graphe de base créé et exporté vers "< voisins[][], int &m){ + int arrete = 0; + for (int i = 0; i < 10; i ++){ + for (int j = 0; j < 10; j ++){ + for (int o = 0; o < 10 ; o ++){ + for (int k = 0; k < 10; k ++){ + if (((o==i+1) && (j==k))|| ((k==j+1) && (i==o)) || ((o==i+1) && (k==j+1))){ + point tmp; + tmp.x=o; + tmp.y=k; + voisins[i][j].push_back(tmp); + tmp.x=i; + tmp.y=j; + voisins[o][k].push_back(tmp); + } + } + } + } + } + } +void affichageGraphique(int n, int m, coord point[], vector voisins[], const char * filename) +// Cree le fichier Exemple.ps qui affiche +// les points et l'arbre de Kruskal. +{ + ofstream output; + output.open(filename,ios::out); + output << "%!PS-Adobe-3.0" << endl; + output << "%%BoundingBox: 0 0 612 792" << endl; + output << endl; + for(int i=0;i<10;i++) + for (int j = 0 ; j < 10; j ++){ + { + output << point[i][j].abs << " " << point[i][j].ord << " 3 0 360 arc" < voisin[], coord point[], int pere[], int m){ + int d[n]; + bool traite[n]; + for (int i =0; i < n; i ++){ + d[i]= -1; + traite[i]=false; + } + pere[0]=0; + d[0]=0; + while (existe(n,d,traite)){ + int current = searchsmallest(n,d,traite); + //cout<<"C'est ti-par avec current = "<< current <(d[x]+distancexy(point[x],point[y]))))){ + d[y]=d[x]+distancexy(point[x],point[y]); + pere[y]=x; + } + } + } +} +int construireArbre(int n,vector voisin[],int pere[]){ + for ( int i = 0; i < n; i ++){ + voisin[i].push_back(pere[i]); + voisin[pere[i]].push_back(i); + } + return n; +} diff --git a/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/tp5 b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/tp5 new file mode 100644 index 0000000..b201576 Binary files /dev/null and b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/tp5 differ diff --git a/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/tp5.cc b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/tp5.cc new file mode 100644 index 0000000..d864773 --- /dev/null +++ b/sem_5/HLIN501_Graphes/TP-DEVOIRTP/TP5/tp5.cc @@ -0,0 +1,243 @@ +#include +#include + +using namespace std; + +const int N=41; +const int INF=9999; //La valeur infinie. +char villes[41][20]={"Amiens", "Angouleme", "Avignon", "Bayonne", "Bilbao", "Bordeaux", "Bourges", "Brest", "Brive", "Bruxelles", "Caen", "Cahors", "Clermont-Ferrand", "Dijon", "Geneve", "Grenoble", "Lille", "Limoges", "Luxembourg", "Lyon", "Marseille", "Millau", "Montpellier", "Mulhouse", "Nancy", "Nantes", "Nice", "Orleans", "Paris", "Perpignan", "Poitiers", "Reims", "Rennes", "Rodez", "Rouen", "Saint-Etienne", "Strasbourg", "Toulouse", "Tours", "Troyes", "Valence"}; + +void floydWarshall(int longueur[][N],int dist[][N],int P[][N]); +void affichage(int dist[][N],int chemin[][N]); +void itineraire(int i,int j,int chemin[][N]); +void itineraireville(int i,int j,int chemin[][N]); +void fermeturetrans(int longueur[][N], int dist[][N], int P[][N], bool fermeture[][N]); +void affichagematrice(int n, bool mat[][N]); + +int main(){ + + int position[41][2]={{282,84},{180,334},{412,443},{140,455},{80,480},{165,389},{304,253},{14,150},{249,365},{380,15},{182,117},{258,412},{322,322},{408,231},{470,287},{464,359},{324,32},{242,332},{470,60},{405,306},{433,480},{339,440},{365,461},{497,208},{453,148},{116,233},{515,460},{277,194},{296,146},{329,505},{208,271},{369,119},{120,175},{330,410},{228,101},{383,339},{508,152},{227,466},{220,230},{363,179},{408,377}}; + + int longueur[41][41]; + for(int i=0;i<41;i++){ + for(int j=0;j<41;j++){ + longueur[i][j]=INF; + } + longueur[i][i]=0; + } + + + longueur[0][34]=120; longueur[0][28]=130; + longueur[0][31]=180; longueur[0][16]=140; + + longueur[1][30]=130; longueur[1][17]=110; + longueur[1][8]=170; longueur[1][5]=120; + + longueur[2][40]=140; longueur[2][22]=90; + longueur[2][20]=90; + + longueur[3][5]=180; longueur[3][37]=300; + longueur[3][4]=70; + + longueur[4][3]=70; + + longueur[5][1]=120; longueur[5][8]=200; longueur[5][11]=230; + longueur[5][37]=241; longueur[5][3]=180; + + longueur[6][27]=121; longueur[6][39]=240; longueur[6][13]=250; + longueur[6][12]=190; longueur[6][38]=230; + + longueur[7][32]=240; + + longueur[8][11]=101; longueur[8][17]=100; longueur[8][1]=170; + longueur[8][5]=200; longueur[8][33]=140; + + longueur[9][16]=110; longueur[9][31]=230; longueur[9][18]=210; + + longueur[10][34]=130; longueur[10][38]=260; longueur[10][32]=180; + + longueur[11][21]=180; longueur[11][8]=101; longueur[11][5]=230; + longueur[11][37]=110; longueur[11][33]=105; + + longueur[12][6]=190; longueur[12][19]=210; longueur[12][35]=150; + longueur[12][17]=230; longueur[12][33]=270; + + longueur[13][19]=200; longueur[13][23]=221; longueur[13][24]=220; + longueur[13][39]=180; longueur[13][6]=250; longueur[13][14]=200; + + longueur[14][15]=145; longueur[14][19]=150; longueur[14][13]=200; + + longueur[15][26]=340; longueur[15][20]=270; longueur[15][40]=90; + longueur[15][19]=150; longueur[15][14]=145; + + longueur[16][0]=140; longueur[16][31]=196; longueur[16][9]=110; + + longueur[17][30]=120; longueur[17][1]=110; longueur[17][8]=100; + longueur[17][12]=230; + + longueur[18][31]=218; longueur[18][36]=220; longueur[18][9]=210; + longueur[18][24]=200; + + longueur[19][40]=150; longueur[19][35]=80; longueur[19][12]=210; + longueur[19][13]=200; longueur[19][14]=150; longueur[19][15]=150; + + longueur[20][22]=170; longueur[20][2]=90; longueur[20][26]=200; + longueur[20][15]=270; + + longueur[21][37]=190; longueur[21][11]=180; longueur[21][22]=110; + longueur[21][33]=60; + + longueur[22][29]=150; longueur[22][37]=240; longueur[22][21]=110; + longueur[22][2]=90; longueur[22][20]=170; longueur[22][40]=200; + + longueur[23][13]=221; longueur[23][24]=170; longueur[23][36]=120; + + longueur[24][36]=160; longueur[24][23]=170; longueur[24][13]=220; + longueur[24][31]=240; longueur[24][18]=200; + + longueur[25][32]=110; longueur[25][38]=210; longueur[25][30]=220; + + longueur[26][20]=200; longueur[26][15]=340; + + longueur[27][6]=121; longueur[27][39]=200; longueur[27][28]=132; + longueur[27][38]=120; + + longueur[28][0]=130; longueur[28][34]=131; longueur[28][27]=132; + longueur[28][39]=181; longueur[28][31]=140; + + longueur[29][37]=210; longueur[29][22]=150; + + longueur[30][25]=220; longueur[30][38]=100; longueur[30][17]=120; + longueur[30][1]=130; + + longueur[31][24]=240; longueur[31][28]=140; longueur[31][39]=130; + longueur[31][0]=180; longueur[31][16]=196; longueur[31][9]=230; + longueur[31][18]=218; + + longueur[32][10]=180; longueur[32][38]=250; longueur[32][7]=240; + longueur[32][25]=110; + + longueur[33][35]=200; longueur[33][40]=225; longueur[33][21]=60; + longueur[33][8]=140; longueur[33][11]=105; longueur[33][12]=270; + + longueur[34][0]=120; longueur[34][28]=131; longueur[34][10]=130; + + longueur[35][12]=150; longueur[35][19]=80; longueur[35][40]=120; + longueur[35][33]=200; + + longueur[36][23]=120; longueur[36][24]=160; longueur[36][18]=220; + + longueur[37][3]=300; longueur[37][5]=241; longueur[37][11]=110; + longueur[37][21]=190; longueur[37][22]=240; longueur[37][29]=210; + + longueur[38][10]=260; longueur[38][32]=250; longueur[38][25]=210; + longueur[38][30]=100; longueur[38][27]=120; longueur[38][6]=230; + + longueur[39][31]=130; longueur[39][28]=181; longueur[39][27]=200; + longueur[39][6]=240; longueur[39][13]=180; + + longueur[40][2]=140; longueur[40][15]=90; longueur[40][35]=120; + longueur[40][19]=150; longueur[40][33]=225; longueur[40][22]=200; + + + + // int longueur[N][N]={{0,2,INF,4,INF}, //Les longueurs des arcs. + // {INF,0,2,INF,INF}, //longueur[i][j]=INF si l'arc ij n'existe pas + // {INF,INF,0,2,INF}, + // {INF,-3,INF,0,2}, + // {2,INF,INF,INF,0}}; + int dist[N][N]; //Le tableau des distances. + int chemin[N][N]; //Le tableau de la premiere etape du chemin de i a j. + floydWarshall(longueur,dist,chemin); + affichage(dist,chemin); + itineraireville(0,5,chemin); + return 0; +} + +void floydWarshall (int longueur[][N],int dist[][N], int P[][N]){ + for (int i =0; i < N; i ++){ + dist[i][i]=0; + P[i][i]=i; + for (int j = 0 ; j < N; j ++){ + if (longueur[i][j]!=INF){ + dist[i][j]=longueur[i][j]; + P[i][j]=j; + } + else { + dist[i][j]=INF; + P[i][j]=-1; + } + } + } + for (int k = 0; k < N; k++){ + for(int i =0; i < N; i ++ ){ + for (int j = 0 ; j < N; j ++){ + if (dist[i][j]>dist[i][k]+dist[k][j]){ + dist[i][j]=dist[i][k]+dist[k][j]; + P[i][j]=P[i][k]; + } + } + } + } + for (int i =0; i < N; i ++){ + if (dist[i][i]<0){ + std::cout<<"Il existe un cycle orienté de poids <0"< +#include + +using namespace std; + +const int N=6; +const int INF=9999; //La valeur infinie. + +void floydWarshall(int longueur[][N],int dist[][N],int P[][N]); +void affichage(int dist[][N],int chemin[][N]); +void itineraire(int i,int j,int chemin[][N]); +void itineraireville(int i,int j,int chemin[][N]); +void fermeturetrans(int longueur[][N], int dist[][N], int P[][N], bool fermeture[][N]); +void affichagematrice(int n, bool mat[][N]); + +int main(){ + int longueur[N][N]={{INF,INF,INF,2,INF,2}, //Les longueurs des arcs. + {2,INF,2,2,INF,INF}, //longueur[i][j]=INF si l'arc ij n'existe pas + {INF,INF,INF,2,INF,INF}, + {INF,INF,INF,INF,2,2}, + {INF,INF,2,INF,INF,2}, + {INF,INF,2,INF,INF,INF}}; + int dist[N][N]; //Le tableau des distances. + int chemin[N][N]; //Le tableau de la premiere etape du chemin de i a j. + bool ferm[N][N]; + fermeturetrans(longueur,dist,chemin,ferm); + affichagematrice(N,ferm); + return 0; +} + +void affichagematrice(int n, bool mat[][N]){ + for (int i = 0; i < n; i ++) { + cout<<"[ "; + for (int j = 0 ; j < n; j ++){ + cout<dist[i][k]+dist[k][j]){ + dist[i][j]=dist[i][k]+dist[k][j]; + P[i][j]=P[i][k]; + fermeture[i][j]=true; + } + } + } + } + for (int i =0; i < N; i ++){ + if (dist[i][i]<0){ + std::cout<<"Il existe un cycle orienté de poids <0"< +#include +#include +#include +using namespace std; + +void ecritureTailles(int n, int m, int comp[]); +void composantes(int n, int m, int edge[][2], int comp[]); +void grapheRandom(int,int, int[][2]); +void printgraphe (int, int, int[][2]); + +int main(int argc, char ** argv) +{ + int n; // Nombre de sommets. + int m; // Nombre d'aretes. + cout << "Entrer le nombre de sommets:"; + cin >> n; + cout << "Entrer le nombre d'aretes:"; + cin >> m; + int edge[m][2]; // Tableau des aretes. + int comp[n]; // comp[i] est le numero de la composante contenant i. + grapheRandom(n,m,edge); + //printgraphe(n,m,edge); + composantes(n,m,edge,comp); + cout<=1){ + cout<<"Il y a "<< tab[i] << " composantes de taille "<< i+1 << " Sommets"< L[n]; + for (int i = 0 ; i < n; i ++) { + comp[i]=i; + taille[i]=1; + L[i].push_back(i); + } + for ( int i = 0 ; i < m; i ++){ + int * x = &comp[edge[i][0]]; + int * y = &comp[edge[i][1]]; + if (*x != *y){ + if (taille[*x]>taille[*y]){ + swap(x,y); + } + int aux = *x; + taille[*y]+=taille[aux]; + for(int j = 0; j < taille[aux]; j ++){ + int tmp = L[aux].back(); + comp[tmp]=*y; + L[*y].push_back(tmp); + L[aux].pop_back(); + } + } + } +} + +void printgraphe (int n, int m, int edge[][2]){ + cout< +#include +#include +#include +#include + +typedef struct coord{int abs; int ord;} coord; +void pointRandom(int n, coord point[]); +void distances(int n, int m, coord point[], int edge[][3]); +void tri(int m, int edge[][3]); +void affichageGraphique(int n, int m, coord point[], int arbre[][2], const char * filename); +void kruskal (int n, int edge[][3], int arbre[][2]); +void fusion(int tableau[][3],int deb1,int fin1,int fin2); +void tri_fusion(int tableau[][3],int longueur); +void tri_fusion_bis(int tableau[][3],int deb,int fin); +using namespace std; + +int +main() +{ + int n; //Le nombre de points. + cout << "Entrer le nombre de points: "; + cin >> n; + int m=n*(n-1)/2; // Le nombre de paires de points. + coord point[n]; // Les coordonnees des points dans le plan. + int edge[m][3]; // Les paires de points et le carre de leur longueur. + int arbre[n-1][2]; // Les aretes de l'arbre de Kruskal. + pointRandom(n,point); + distances(n,m,point,edge); + tri_fusion(edge,m); + // for (int i =0; i < m; i ++){ + // cout << "point "<< edge[i][0]<<":"<0) + { + tri_fusion_bis(tableau,0,longueur-1); + } + } +void tri(int m, int edge[][3]){ + for (int i = 0 ; i < m ; i ++){ + for(int j=i+1; j < m; j ++){ + if ( edge[i][2]>edge[j][2]){ + swap(edge[i][0],edge[j][0]); + swap(edge[i][1],edge[j][1]); + swap(edge[i][2],edge[j][2]); + } + } + } +} + +void affichageGraphique(int n, int m, coord point[], int arbre[][2], const char * filename) +// Cree le fichier Exemple.ps qui affiche +// les points et l'arbre de Kruskal. +{ + ofstream output; + output.open(filename,ios::out); + output << "%!PS-Adobe-3.0" << endl; + output << "%%BoundingBox: 0 0 612 792" << endl; + output << endl; + for(int i=0;i +#include +#include +#include +#include + +typedef struct coord{int abs; int ord;} coord; +void pointRandom(int n, coord point[]); +void distances(int n, int m, coord point[], int edge[][3]); +void tri(int m, int edge[][3]); +void affichageGraphique(int n, int m, coord point[], int arbre[][2], const char * filename); +void kruskal (int n, int edge[][3], int arbre[][2]); +void fusion(int tableau[][3],int deb1,int fin1,int fin2); +void tri_fusion(int tableau[][3],int longueur); +void tri_fusion_bis(int tableau[][3],int deb,int fin); +using namespace std; + +int +main() +{ + int n; //Le nombre de points. + cout << "Entrer le nombre de points: "; + cin >> n; + int m=n*(n-1)/2; // Le nombre de paires de points. + coord point[n]; // Les coordonnees des points dans le plan. + int edge[m][3]; // Les paires de points et le carre de leur longueur. + int arbre[n-1][2]; // Les aretes de l'arbre de Kruskal. + pointRandom(n,point); + distances(n,m,point,edge); + tri(m,edge); + for (int i =0; i < m; i ++){ + cout << "point "<< edge[i][0]<<":"<0) + { + tri_fusion_bis(tableau,0,longueur-1); + } + } +void tri(int m, int edge[][3]){ + for (int i = 0 ; i < m ; i ++){ + for(int j=i+1; j < m; j ++){ + if ( edge[i][2]>edge[j][2]){ + swap(edge[i][0],edge[j][0]); + swap(edge[i][1],edge[j][1]); + swap(edge[i][2],edge[j][2]); + } + } + } +} + +void affichageGraphique(int n, int m, coord point[], int arbre[][2], const char * filename) +// Cree le fichier Exemple.ps qui affiche +// les points et l'arbre de Kruskal. +{ + ofstream output; + output.open(filename,ios::out); + output << "%!PS-Adobe-3.0" << endl; + output << "%%BoundingBox: 0 0 612 792" << endl; + output << endl; + for(int i=0;i +#include +#include +#include +#include +#include +#include +#include + +typedef struct coord{int abs; int ord;} coord; +bool search (std::vector vec, int x); +void ecritureNiveaux(int n, int niveau[]); +void voisinsRandom(int n, int m, std::vectorvoisins[]); +void afficheGraph (int n, std::vectorvoisins[]); +void parcoursLargeur(int n, std::vectorvoisins[],int niveau[], int ordre[], int pere[]); +void afficheArbre(int n, int pere[], int ordre[]); +void pacoursProf(int n, int r, std::vector*> voisins, int debut[],int fin[], int pere[], int niveau[]); +void vectortostack(int n,std::vector arch[], std::vector* > young); +void afficheArbrebis(int n, int pere[]); +using namespace std; + +void voisinsRandom(int n, int m, vectorvoisins[]){ + srand(time(NULL)); + int x=1; int y=0; + for (int i = 0; i < m; i ++){ + do { + x = rand()%n; + y = rand()%n; + while (x==y){ + y = rand()%n; + } + } while (search(voisins[x],y)); + voisins[x].push_back(y); + voisins[y].push_back(x); + } +} +bool search (vector vec, int x){ + int i = 0; + if (vec.size()==0){ + return false; + } + while (vec[i]!=x){ + i ++; + if (i>vec.size()){ + return false; + } + } + return true; +} +int main() { + int n; //Le nombre de points. + int m; // nb aretes + cout << "Entrer le nombre de points: "; + cin >> n; + cout << "Entrer le nombre d'aretes: "; + cin>>m; + if (m > n*(n-1)/2){ + cout<<"Nombre d'aretes trop grand, cap à : "<< n*(n-1)/2< voisins[n]; + int pere[n]; + int ordre[n]; + int niveau[n]; + int niveau2[n]; + int debut[n]; + int fin[n]; + vector* > piledevoisins = vector< stack < int > * >(n); + for (int i =0; i < n; i ++){ + piledevoisins[i]=new stack; + } + // for (int i = 0; i < n ; i ++){ + // piledevoisins[i]=new stack; + // } + voisinsRandom(n,m,voisins); + afficheGraph(n,voisins); + parcoursLargeur(n,voisins,niveau,ordre,pere); + afficheArbre(n, pere, ordre); + //ecritureNiveaux(n,niveau); + cout<<"Parcours en profondeur OK"<voisins[]){ + for (int i =0; i < n; i ++){ + int j = 0; + cout<<"Sommet "<j){ + cout<< " "<voisins[],int niveau[], int ordre[], int pere[]){ + int dejavu[n]; + for (int i =0; i < n; i ++ ){ + dejavu[i]=0; + } + int r=0; + dejavu[r]=1; + ordre[r]=1; + pere[r]=r; + niveau[r]=0; + queue AT; + AT.push(r); + int t = 2; + while (!AT.empty()){ + int v = AT.front(); + AT.pop(); + for (int i =0; i < voisins[v].size();i ++){ + int x = voisins[v][i]; + if (!dejavu[x]){ + dejavu[x]=1; + AT.push(x); + ordre[x]=t; + t ++; + pere[x]=v; + niveau[x]=niveau[v]+1; + } + } + } +} +void pacoursProf(int n, int r, vector* > voisins, int debut[],int fin[], int pere[] ,int niveau[]){ + int dejavu[n]; + for (int i =0; i < n; i ++ ){ + dejavu[i]=0; + } + dejavu[r]=1; + debut[r]=1; + pere[r]=r; + niveau[r]=0; + stack AT; + AT.push(r); + int t = 2; + while (!AT.empty()){ + int x = AT.top(); + if (voisins[x]->empty()){ + AT.pop(); + fin[x]=t; + t ++; + } + else { + int y = voisins[x]->top(); + voisins[x]->pop(); + if (!dejavu[y]){ + dejavu[y]=1; + AT.push(y); + debut[y]=t; + t++; + pere[y]=x; + niveau[y]=niveau[x]+1; + cout << "Niveau de "< +#include +#include +#include +#include + +using namespace std; + +const int N=1400; +const int M=(N*(N-1))/2; + +typedef struct coord{int abs; int ord;} coord; + +void pointRandom(int n,coord point[]); +float distancexy(coord p1,coord p2); +void voisins(int n,int dmax,coord point[],vector voisin[],int &m); +void voisins2arete(int n,vectorvoisins[],int arete[][2]); +void affichageGraphique(int n,int m,coord point[],vector voisins[],const char * name); +bool existe(int n,int dis[],bool traite[]); +int searchsmallest(int n, int dist[],bool traite[]); +void dijkstra(int n,vector voisin[],coord point[],int pere[], int m); +int construireArbre(int n,vector voisin[],int pere[]); + +int +main() +{ + int n; // Le nombre de points. + cout << "Entrer le nombre de points: "; + cin >> n; + int dmax=50; // La distance jusqu'a laquelle on relie deux points. + coord point[N]; // Les coordonnees des points. + vector voisin[N]; + vector voisinbis[N]; // Les listes de voisins. + int arbre[N-1][2]; // Les aretes de l'arbre de Dijkstra. + int pere[N]; // La relation de filiation de l'arbre de Dijkstra. + int m; // Le nombre d'aretes + int arete[M][2]; // Les aretes du graphe + pointRandom(n,point); + voisins(n,dmax, point, voisin, m); + const char * filename = "affichage.ps"; + affichageGraphique(n,m,point,voisin,filename); + cout<<"Graphe de base créé et exporté vers "< voisins[], int &m){ + int arrete = 0; + for (int i = 0; i < n; i ++){ + for (int j = i+1; j < n; j ++){ + if ( sqrt(pow(point[i].abs-point[j].abs,2)+pow(point[i].ord-point[j].ord,2))<=dmax){ + voisins[i].push_back(j); + voisins[j].push_back(i); + arrete++; + } + } + } + m=arrete; +} + +void affichageGraphique(int n, int m, coord point[], vector voisins[], const char * filename) +// Cree le fichier Exemple.ps qui affiche +// les points et l'arbre de Kruskal. +{ + ofstream output; + output.open(filename,ios::out); + output << "%!PS-Adobe-3.0" << endl; + output << "%%BoundingBox: 0 0 612 792" << endl; + output << endl; + for(int i=0;i= i){ + output << point[i].abs<<" "< voisin[], coord point[], int pere[], int m){ + int d[n]; + bool traite[n]; + for (int i =0; i < n; i ++){ + d[i]= -1; + traite[i]=false; + } + pere[0]=0; + d[0]=0; + while (existe(n,d,traite)){ + int current = searchsmallest(n,d,traite); + //cout<<"C'est ti-par avec current = "<< current <(d[x]+distancexy(point[x],point[y]))))){ + d[y]=d[x]+distancexy(point[x],point[y]); + pere[y]=x; + } + } + } +} +int construireArbre(int n,vector voisin[],int pere[]){ + for ( int i = 0; i < n; i ++){ + voisin[i].push_back(pere[i]); + voisin[pere[i]].push_back(i); + } + return n; +} diff --git a/sem_5/HLIN501_Graphes/TP/TP5/tp5 b/sem_5/HLIN501_Graphes/TP/TP5/tp5 new file mode 100644 index 0000000..b201576 Binary files /dev/null and b/sem_5/HLIN501_Graphes/TP/TP5/tp5 differ diff --git a/sem_5/HLIN501_Graphes/TP/TP5/tp5.cc b/sem_5/HLIN501_Graphes/TP/TP5/tp5.cc new file mode 100644 index 0000000..d864773 --- /dev/null +++ b/sem_5/HLIN501_Graphes/TP/TP5/tp5.cc @@ -0,0 +1,243 @@ +#include +#include + +using namespace std; + +const int N=41; +const int INF=9999; //La valeur infinie. +char villes[41][20]={"Amiens", "Angouleme", "Avignon", "Bayonne", "Bilbao", "Bordeaux", "Bourges", "Brest", "Brive", "Bruxelles", "Caen", "Cahors", "Clermont-Ferrand", "Dijon", "Geneve", "Grenoble", "Lille", "Limoges", "Luxembourg", "Lyon", "Marseille", "Millau", "Montpellier", "Mulhouse", "Nancy", "Nantes", "Nice", "Orleans", "Paris", "Perpignan", "Poitiers", "Reims", "Rennes", "Rodez", "Rouen", "Saint-Etienne", "Strasbourg", "Toulouse", "Tours", "Troyes", "Valence"}; + +void floydWarshall(int longueur[][N],int dist[][N],int P[][N]); +void affichage(int dist[][N],int chemin[][N]); +void itineraire(int i,int j,int chemin[][N]); +void itineraireville(int i,int j,int chemin[][N]); +void fermeturetrans(int longueur[][N], int dist[][N], int P[][N], bool fermeture[][N]); +void affichagematrice(int n, bool mat[][N]); + +int main(){ + + int position[41][2]={{282,84},{180,334},{412,443},{140,455},{80,480},{165,389},{304,253},{14,150},{249,365},{380,15},{182,117},{258,412},{322,322},{408,231},{470,287},{464,359},{324,32},{242,332},{470,60},{405,306},{433,480},{339,440},{365,461},{497,208},{453,148},{116,233},{515,460},{277,194},{296,146},{329,505},{208,271},{369,119},{120,175},{330,410},{228,101},{383,339},{508,152},{227,466},{220,230},{363,179},{408,377}}; + + int longueur[41][41]; + for(int i=0;i<41;i++){ + for(int j=0;j<41;j++){ + longueur[i][j]=INF; + } + longueur[i][i]=0; + } + + + longueur[0][34]=120; longueur[0][28]=130; + longueur[0][31]=180; longueur[0][16]=140; + + longueur[1][30]=130; longueur[1][17]=110; + longueur[1][8]=170; longueur[1][5]=120; + + longueur[2][40]=140; longueur[2][22]=90; + longueur[2][20]=90; + + longueur[3][5]=180; longueur[3][37]=300; + longueur[3][4]=70; + + longueur[4][3]=70; + + longueur[5][1]=120; longueur[5][8]=200; longueur[5][11]=230; + longueur[5][37]=241; longueur[5][3]=180; + + longueur[6][27]=121; longueur[6][39]=240; longueur[6][13]=250; + longueur[6][12]=190; longueur[6][38]=230; + + longueur[7][32]=240; + + longueur[8][11]=101; longueur[8][17]=100; longueur[8][1]=170; + longueur[8][5]=200; longueur[8][33]=140; + + longueur[9][16]=110; longueur[9][31]=230; longueur[9][18]=210; + + longueur[10][34]=130; longueur[10][38]=260; longueur[10][32]=180; + + longueur[11][21]=180; longueur[11][8]=101; longueur[11][5]=230; + longueur[11][37]=110; longueur[11][33]=105; + + longueur[12][6]=190; longueur[12][19]=210; longueur[12][35]=150; + longueur[12][17]=230; longueur[12][33]=270; + + longueur[13][19]=200; longueur[13][23]=221; longueur[13][24]=220; + longueur[13][39]=180; longueur[13][6]=250; longueur[13][14]=200; + + longueur[14][15]=145; longueur[14][19]=150; longueur[14][13]=200; + + longueur[15][26]=340; longueur[15][20]=270; longueur[15][40]=90; + longueur[15][19]=150; longueur[15][14]=145; + + longueur[16][0]=140; longueur[16][31]=196; longueur[16][9]=110; + + longueur[17][30]=120; longueur[17][1]=110; longueur[17][8]=100; + longueur[17][12]=230; + + longueur[18][31]=218; longueur[18][36]=220; longueur[18][9]=210; + longueur[18][24]=200; + + longueur[19][40]=150; longueur[19][35]=80; longueur[19][12]=210; + longueur[19][13]=200; longueur[19][14]=150; longueur[19][15]=150; + + longueur[20][22]=170; longueur[20][2]=90; longueur[20][26]=200; + longueur[20][15]=270; + + longueur[21][37]=190; longueur[21][11]=180; longueur[21][22]=110; + longueur[21][33]=60; + + longueur[22][29]=150; longueur[22][37]=240; longueur[22][21]=110; + longueur[22][2]=90; longueur[22][20]=170; longueur[22][40]=200; + + longueur[23][13]=221; longueur[23][24]=170; longueur[23][36]=120; + + longueur[24][36]=160; longueur[24][23]=170; longueur[24][13]=220; + longueur[24][31]=240; longueur[24][18]=200; + + longueur[25][32]=110; longueur[25][38]=210; longueur[25][30]=220; + + longueur[26][20]=200; longueur[26][15]=340; + + longueur[27][6]=121; longueur[27][39]=200; longueur[27][28]=132; + longueur[27][38]=120; + + longueur[28][0]=130; longueur[28][34]=131; longueur[28][27]=132; + longueur[28][39]=181; longueur[28][31]=140; + + longueur[29][37]=210; longueur[29][22]=150; + + longueur[30][25]=220; longueur[30][38]=100; longueur[30][17]=120; + longueur[30][1]=130; + + longueur[31][24]=240; longueur[31][28]=140; longueur[31][39]=130; + longueur[31][0]=180; longueur[31][16]=196; longueur[31][9]=230; + longueur[31][18]=218; + + longueur[32][10]=180; longueur[32][38]=250; longueur[32][7]=240; + longueur[32][25]=110; + + longueur[33][35]=200; longueur[33][40]=225; longueur[33][21]=60; + longueur[33][8]=140; longueur[33][11]=105; longueur[33][12]=270; + + longueur[34][0]=120; longueur[34][28]=131; longueur[34][10]=130; + + longueur[35][12]=150; longueur[35][19]=80; longueur[35][40]=120; + longueur[35][33]=200; + + longueur[36][23]=120; longueur[36][24]=160; longueur[36][18]=220; + + longueur[37][3]=300; longueur[37][5]=241; longueur[37][11]=110; + longueur[37][21]=190; longueur[37][22]=240; longueur[37][29]=210; + + longueur[38][10]=260; longueur[38][32]=250; longueur[38][25]=210; + longueur[38][30]=100; longueur[38][27]=120; longueur[38][6]=230; + + longueur[39][31]=130; longueur[39][28]=181; longueur[39][27]=200; + longueur[39][6]=240; longueur[39][13]=180; + + longueur[40][2]=140; longueur[40][15]=90; longueur[40][35]=120; + longueur[40][19]=150; longueur[40][33]=225; longueur[40][22]=200; + + + + // int longueur[N][N]={{0,2,INF,4,INF}, //Les longueurs des arcs. + // {INF,0,2,INF,INF}, //longueur[i][j]=INF si l'arc ij n'existe pas + // {INF,INF,0,2,INF}, + // {INF,-3,INF,0,2}, + // {2,INF,INF,INF,0}}; + int dist[N][N]; //Le tableau des distances. + int chemin[N][N]; //Le tableau de la premiere etape du chemin de i a j. + floydWarshall(longueur,dist,chemin); + affichage(dist,chemin); + itineraireville(0,5,chemin); + return 0; +} + +void floydWarshall (int longueur[][N],int dist[][N], int P[][N]){ + for (int i =0; i < N; i ++){ + dist[i][i]=0; + P[i][i]=i; + for (int j = 0 ; j < N; j ++){ + if (longueur[i][j]!=INF){ + dist[i][j]=longueur[i][j]; + P[i][j]=j; + } + else { + dist[i][j]=INF; + P[i][j]=-1; + } + } + } + for (int k = 0; k < N; k++){ + for(int i =0; i < N; i ++ ){ + for (int j = 0 ; j < N; j ++){ + if (dist[i][j]>dist[i][k]+dist[k][j]){ + dist[i][j]=dist[i][k]+dist[k][j]; + P[i][j]=P[i][k]; + } + } + } + } + for (int i =0; i < N; i ++){ + if (dist[i][i]<0){ + std::cout<<"Il existe un cycle orienté de poids <0"< +#include + +using namespace std; + +const int N=6; +const int INF=9999; //La valeur infinie. + +void floydWarshall(int longueur[][N],int dist[][N],int P[][N]); +void affichage(int dist[][N],int chemin[][N]); +void itineraire(int i,int j,int chemin[][N]); +void itineraireville(int i,int j,int chemin[][N]); +void fermeturetrans(int longueur[][N], int dist[][N], int P[][N], bool fermeture[][N]); +void affichagematrice(int n, bool mat[][N]); + +int main(){ + int longueur[N][N]={{INF,INF,INF,2,INF,2}, //Les longueurs des arcs. + {2,INF,2,2,INF,INF}, //longueur[i][j]=INF si l'arc ij n'existe pas + {INF,INF,INF,2,INF,INF}, + {INF,INF,INF,INF,2,2}, + {INF,INF,2,INF,INF,2}, + {INF,INF,2,INF,INF,INF}}; + int dist[N][N]; //Le tableau des distances. + int chemin[N][N]; //Le tableau de la premiere etape du chemin de i a j. + bool ferm[N][N]; + fermeturetrans(longueur,dist,chemin,ferm); + affichagematrice(N,ferm); + return 0; +} + +void affichagematrice(int n, bool mat[][N]){ + for (int i = 0; i < n; i ++) { + cout<<"[ "; + for (int j = 0 ; j < n; j ++){ + cout<dist[i][k]+dist[k][j]){ + dist[i][j]=dist[i][k]+dist[k][j]; + P[i][j]=P[i][k]; + fermeture[i][j]=true; + } + } + } + } + for (int i =0; i < N; i ++){ + if (dist[i][i]<0){ + std::cout<<"Il existe un cycle orienté de poids <0"<