Ayuda con algoritmo de floyd warshall urgente!!
Publicado por Luis (5 intervenciones) el 22/02/2020 04:54:42
tengo este codigo la verdad no estoy seguro de si es correcto en su totalidad, soy algo nuevo en esto.
3 archivos
en el main no tengo nada porque intente hacer el algoritmo de warshall pero no se como hacerlo o como empezar.
pregunte y solo me dijeron que es una funcion que no pertenece a la clase pero que si utiliza la clase, la verdad no entendí
y tengo que programar este código pero no se como hacerlo , intente con objetos dinamicos, y otras formas pero no se como hacerlo, si me pudieran orientar a como ejecutarlo y en donde se los agradeceria mucho, URGE tengo que entregar esto antes de las 12:00 am
*************** algoritmo a ejecutar
Algoritmo del camino mínimo
Un dígrafo con pesos G de M nodos está en memoria mediante una matriz de pesos W. Este
algoritmo encuentra la matriz Q tal que [I, J] es la longitud del camino mínimo del nodo VI al nodo
VJ. Infinito es un número muy grande y MIN es la función del valor mínimo.
1. [Iniciar Q]
Repetir Para I = 1, 2,…, M:
Repetir Para J = 1, 2,…, M:
Si W[I, J] = 0 entonces
Hacer Q[I, J] := Infinito
Sino
Hacer Q[I, J] := W[I, J]
[fin del bucle]
[fin del bucle]
2. [Actualizar Q:]
Repetir pasos 3 y 4 para K = 1,2,…, M:
3. Repetir paso 4 para I = 1,2,…, M:
4. Repetir para J = 1,2,…, M:
Hacer Q[I, J] := MIN( Q[I, J], Q[I, K] + Q[K , J])
[fin del bucle]
[fin del bucle]
[fin del bucle]
5. [Salir]
la matriz de pesos es ********************
[ 7 5 0 0 ]
[ 7 0 0 2 ]
[ 0 3 0 0 ]
[ 4 0 1 0 ]
3 archivos
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
*******************MatrizQ.cpp******************
#include "MatrizQ.h"MatrizQ::MatrizQ(int tamanio)
{this->tamanio=tamanio;
this->matriz=NULL;
matriz=new int*[tamanio];
for(int i=0;i<tamanio;i++)
{matriz[i]=new int[tamanio];
}for(int i=0;i<this->tamanio;i++)
{cout<<endl;
for(int j=0;j<this->tamanio;j++)
{matriz[i][j]=0;
} } }MatrizQ::~MatrizQ()
{liberaMemoria();
}int MatrizQ::dameTuTamanio()
{cin>>this->tamanio;
return this->tamanio;
}void MatrizQ::verificaTusDatos()
{if(this->tamanio<0)
{cout<<"el tamanio de la matriz no puede ser negativo, por favor ingresa otro valor: ";
} }void MatrizQ::pideleAlUsuariosTusDatos()
{if(matriz!=NULL)
{for(int i=0;i<this->tamanio;i++)
delete []matriz[i];
delete []matriz;
}cout<<endl<<"Dame el orden de la matriz A"<<endl<<"tamanio: ";
do
{this->dameTuTamanio();
this->verificaTusDatos();
}while(this->tamanio<0);
/**RESERVA DE MEMORIA DINAMICA*/matriz=new int*[this->tamanio];
for(int i=0;i<=this->tamanio;i++)
{matriz[i]=new int[this->tamanio];
} /**LECTURA DE LOS DATOS DE LA MATRIZ*/cout<<"ingresa los datos de la matriz"<<endl;
for(int i=0;i<this->tamanio;i++)
{for(int j=0;j<this->tamanio;j++)
{cout<<"ingresa el dato en la posicion ["<<i+1<<"]["<<j+1<<"]:";
cin>>matriz[i][j];
} } }void MatrizQ::muestraTusDatos()
{for(int i=0;i<this->tamanio;i++)
{cout<<endl;
for(int j=0;j<this->tamanio;j++)
{cout<<"["<<matriz[i][j]<<"] ";
} }cout<<endl;
}int MatrizQ::dameTuDatoRC(int renglon, int columna)
{ renglon=renglon; columna=columna;if(renglon<0||columna<0)
{cout<<"no hay renglones ni columnas negativas"<<endl;
}return matriz[renglon][columna];
}void MatrizQ::modificaTuDatoRC(int renglon, int columna, int valor)
{ renglon=renglon; columna=columna;this->matriz[renglon][columna]=valor;
}MatrizQ& MatrizQ::operator=(MatrizQ Q)
{if(this!=&Q)
{tamanio=Q.tamanio;
delete [] this->matriz;
this->tamanio=Q.tamanio;
this->matriz = new int *[this->tamanio];
for(int i=0; i<this->tamanio; i++)
{this->matriz[i] = new int[tamanio];
for(int j=0; j<this->tamanio; j++)
this->matriz[i][j] = Q.matriz[i][j];
} }else
{ matriz=NULL;for(int i=0; i<this->tamanio; i++)
{for(int j=0; j<this->tamanio; j++)
this->matriz[i][j] = Q.matriz[i][j];
} } /**++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/for(int i=0;i<this->tamanio;i++)
{for(int j=0;j<this->tamanio;j++)
modificaTuDatoRC(i,j,Q.dameTuDatoRC(i,j));
} return *this; }void MatrizQ::liberaMemoria()
{if(matriz!=NULL)
{for(int i=0;i<this->tamanio;i++)
delete []matriz[i];
delete []matriz;
} }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
/*****************MatrizQ.h**************#ifndef MATRIZQ_H#define MATRIZQ_H#include<iostream>using namespace std;class MatrizQ{ public: MatrizQ(int tamanio = 0); ~MatrizQ();//////////////////////////////////////////////// void pideleAlUsuariosTusDatos(void); void muestraTusDatos(void); int dameTuDatoRC(int renglon, int columna); int dameTuTamanio(void); void modificaTuDatoRC(int renglon, int columna, int valor); MatrizQ& operator=(MatrizQ Q);////////////////////////////////// friend void cam_min(MatrizQ **W, MatrizQ **Q0 ); private: void verificaTusDatos(void); void liberaMemoria(void);//////////////////////////// int** matriz; int tamanio;};#endif // MATRIZQ_Hen el main no tengo nada porque intente hacer el algoritmo de warshall pero no se como hacerlo o como empezar.
pregunte y solo me dijeron que es una funcion que no pertenece a la clase pero que si utiliza la clase, la verdad no entendí
y tengo que programar este código pero no se como hacerlo , intente con objetos dinamicos, y otras formas pero no se como hacerlo, si me pudieran orientar a como ejecutarlo y en donde se los agradeceria mucho, URGE tengo que entregar esto antes de las 12:00 am
*************** algoritmo a ejecutar
Algoritmo del camino mínimo
Un dígrafo con pesos G de M nodos está en memoria mediante una matriz de pesos W. Este
algoritmo encuentra la matriz Q tal que [I, J] es la longitud del camino mínimo del nodo VI al nodo
VJ. Infinito es un número muy grande y MIN es la función del valor mínimo.
1. [Iniciar Q]
Repetir Para I = 1, 2,…, M:
Repetir Para J = 1, 2,…, M:
Si W[I, J] = 0 entonces
Hacer Q[I, J] := Infinito
Sino
Hacer Q[I, J] := W[I, J]
[fin del bucle]
[fin del bucle]
2. [Actualizar Q:]
Repetir pasos 3 y 4 para K = 1,2,…, M:
3. Repetir paso 4 para I = 1,2,…, M:
4. Repetir para J = 1,2,…, M:
Hacer Q[I, J] := MIN( Q[I, J], Q[I, K] + Q[K , J])
[fin del bucle]
[fin del bucle]
[fin del bucle]
5. [Salir]
la matriz de pesos es ********************
[ 7 5 0 0 ]
[ 7 0 0 2 ]
[ 0 3 0 0 ]
[ 4 0 1 0 ]
Valora esta pregunta
0
