Initial commit

1 files changed, 74 insertions, 0 deletions

diff --git a/sem_5/HLIN501_Graphes/TP/TP5/tp50.cc b/sem_5/HLIN501_Graphes/TP/TP5/tp50.cc
new file mode 100644
index 0000000..a4566d0
--- /dev/null
+++ b/sem_5/HLIN501_Graphes/TP/TP5/tp50.cc
@@ -0,0 +1,74 @@
+#include <iostream>
+#include <vector>
+
+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<<mat[i][j]<<" , ";
+    }
+    cout << " ]"<<endl;
+  }
+}
+
+void fermeturetrans(int longueur[][N], int dist[][N], int P[][N], bool fermeture[][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;
+        fermeture[i][j]=true;
+      }
+      else {
+        dist[i][j]=INF;
+        P[i][j]=-1;
+        fermeture[i][j]=false;
+      }
+    }
+  }
+    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];
+            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"<<endl;
+      }
+    }
+  }