1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
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;
}
}
}
|
