Ayuda con implementacion algoritmo warshall en C
luar79:
Hola,
necesito ayuda para implementar el algoritmo warshall, que ira recogiendo varias filas con dos ciudades, que se suponen que entre todas las ciudades hay conexion pasando a traves de otras. Entonces se busca con este algoritmo que vaya indicando si en cada fila devuelva true o false segun vaya recorriendo las filas. Yo al menos he entendido asi el problema.
El primer problema que tengo es que, no consigo crear la matriz dinamica para guardar las ciudades en cada fila de la matriz, al leer de nuevo el fichero de texto se cuelga el programa, y no veo la razon. Vereis que he puesto varios printf(variable), para ver donde se quedaba colgado el programa, y muestra por pantalla el numero de filas.
Y despues lo que no se es, en que tipo de variable debo recoger los resultados? en una matriz de tipo int?, y si es asi luego es ir recorriendo la matriz viendo cuantos 1, obtiene?y como discernir que por el numero de 1 que devuelve el algoritmo, no hay ninguna ciudad aislada?. Como imaginareis es un ejercicio que me han puesto, y estoy bloqueado desde hace dias haciendo pruebas. Pego el codigo:
Código
void warshall (bool *c, bool *a, unsigned int nNodos)
{
int i,j,k;
for (i = 0; i < nNodos; i++)
for (j=0; j< nNodos; j++)
//A[i][j] = C[i][j];
a[(i*nNodos)+j] = c[(i*nNodos)+j];
for (k = 0; k < nNodos; k++)
for (i = 0; i < nNodos; i++)
for (j=0; j< nNodos; j++)
//A[i][j] = A[i][j] || A[i][k] && A[k][j]; //Si hay un camino de ‘i’ a ‘j’ o si hay //un camino de ‘i’ a ‘j’ pasando por ‘k’
a[(i*nNodos)+j] = a[(i*nNodos)+j] || a[(i*nNodos)+k] && a[(k*nNodos)+j]; //Si hay un camino de ‘i’ a ‘j’ o si hay //un camino de ‘i’ a ‘j’ pasando por ‘k’
}
int main()
{
FILE *fichero;
bool *a;
bool *test;
int n_Nodos=19;
char * campo;
char ** datos;
int filas=0;
int MaxLinea=maxLinea;
char lineaFinal[maxLinea];
char ciudad1[maxCiudad];
char ciudad2[maxCiudad];
char distancia[maxCiudad];
char linea[maxLinea];
fichero= fopen( "carreteras.txt", "r");
if(fichero==NULL)
{
printf("No se ha podido abrir el fichero.\n");
exit(1);
}
else
{
while(fgets(linea,MaxLinea,fichero))
{
filas++;
}
printf("%d\n",filas);
fichero= fopen( "carreteras.txt", "r");
datos=malloc(sizeof(char*)*filas);
datos=malloc(sizeof(char)*3);
// se lee cada fila de todo el fichero de elementos
while(fscanf(fichero, "%s %s %s", ciudad1, ciudad2, distancia) == 3)
{
datos[filas][0]=ciudad1;
printf("El valor de la linea %s \n", ciudad1);
datos[filas][1]=ciudad2;
printf("El valor de la linea %s \n", ciudad2);
datos[filas][2]=distancia;
printf("El valor de la linea %s \n", distancia);
}
}
getchar();
a = (bool *)malloc(sizeof(bool)*(n_Nodos * n_Nodos));
// aqui no tengo claro si se recoge asi los resultados del algoritmo
int resul[filas][3]=warshall (a,datos,n_Nodos);
return 0;
}
Muchas gracias por la ayuda!
MAFUS:
Pasa por aquí una copia del archivo de texto que usas.
luar79:
Vale, gracias:
Corunya Vigo 171
Corunya Valladolid 455
Vigo Valladolid 356
Valladolid Bilbao 280
Valladolid Madrid 193
Oviedo Bilbao 304
Bilbao Madrid 395
Bilbao Zaragoza 324
Madrid Zaragoza 325
Zaragoza Barcelona 296
Barcelona Gerona 100
Valencia Barcelona 349
Madrid Badajoz 403
Madrid Jaen 335
Madrid Albacete 251
Albacete Valencia 191
Albacete Murcia 150
Murcia Granada 284
Murcia Valencia 241
Granada Jaen 99
Granada Sevilla 256
Jaen Sevilla 242
Sevilla Cadiz 125
K-YreX:
Citar
Ahora estoy que no se como en una matriz dinamica de cadenas de texto, compararla con una cadena de texto que seria una ciudad, y si coincide el campo de la matriz, se le da un valor numerico a esa ciudad
Este problema está ya mencionado en el otro tema que abriste para esto mismo: https://foro.elhacker.net/programacion_cc/ayuda_con_fichero_y_cadenas_en_c-t514770.0.html
Citar
Me ha mostrado una tabla con 1 y 0, aunque no se si acertaba bien en las conexiones de los nodos
Si no me he equivocado, esta matriz representa el número de ciudades por las que tienes que pasar para llegar desde la ciudad i hasta la ciudad j. (Por si te fias y quieres comparar)
(0 = ya estás en esa ciudad | -1 = no se puede llegar de la ciudad i a la ciudad j)
Código:
[INFO ] ---------- NODE LIST ----------
[ 0 - Corunya]
[ 1 - Vigo]
[ 2 - Valladolid]
[ 3 - Bilbao]
[ 4 - Madrid]
[ 5 - Oviedo]
[ 6 - Zaragoza]
[ 7 - Barcelona]
[ 8 - Gerona]
[ 9 - Valencia]
[10 - Badajoz]
[11 - Jaen]
[12 - Albacete]
[13 - Murcia]
[14 - Granada]
[15 - Sevilla]
[16 - Cadiz]
[INFO ] -------------------- WARSHALL MATRIX --------------------
0 1 1 2 2 -1 3 4 5 4 3 3 3 4 5 4 5
-1 0 1 2 2 -1 3 4 5 4 3 3 3 4 5 4 5
-1 -1 0 1 1 -1 2 3 4 3 2 2 2 3 4 3 4
-1 -1 -1 0 1 -1 1 2 3 3 2 2 2 3 4 3 4
-1 -1 -1 -1 0 -1 1 2 3 2 1 1 1 2 3 2 3
-1 -1 -1 1 2 0 2 3 4 4 3 3 3 4 5 4 5
-1 -1 -1 -1 -1 -1 0 1 2 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 0 1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 1 2 0 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 -1 -1 -1 1 2
-1 -1 -1 -1 -1 -1 -1 2 3 1 -1 3 0 1 2 3 4
-1 -1 -1 -1 -1 -1 -1 2 3 1 -1 2 -1 0 1 2 3
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 0 1 2
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0
PD: Está hecho con el método mencionado en el otro tema al que hacía referencia. :rolleyes:
Y otras cosillas:
A la función contar_filas() no necesitas pasarle filas/columnas como parámetros.
Basta con que pases el nombre del fichero y devuelvas con un return el número de filas. Debería quedar algo así:
PD: Además debería limitarse a contar filas, no a "contar columnas" (cosa que no hace muy bien pues le has puesto el número de strtok() que tiene que hacer a mano)Código
int contar_filas(char *nombre_fichero);
Las funciones auxiliares no deberían mostrar mensajes por pantalla a no ser que estén diseñadas específicamente para eso.
En la función contar_filas() por ejemplo, quedaría mejor devolver un -1 si no se puede abrir el fichero sin mostrar ningún mensaje ni salir con un exit()
Lo mismo para la función warshall(). Deja sólo la primera parte que modifica la matriz y luego muéstrala desde el main() o desde una función mostrar_matriz().
Los cambios que hagas en la matriz se mantendrán fuera también por lo que ten en cuenta que una vez llamas a warshall() has perdido tu matriz original. De la parte del main() se te simplificaría utilizando la solución del enlace que hay al principio.
Además:
No necesitas declarar filas/columnas como punteros. Utiliza constantes en lugar de número sueltos (ej: 17) Línea 82 -> Cuidado: Las multiplicaciones/divisiones se hacen antes que las sumas/restas (necesitas usar paréntesis)
Y por qué crear una matriz con 1 columna menos que el número de columnas que has "contado"?? Ahí algo de lógica está fallando Línea 90 -> Cuidado: Estás guardando el valor de 'ciudad2' otra vez La última parte sobra por completo
Con eso yo creo que quedaría todo comentado :silbar: :silbar:
luar79:
Hola!,
perdona no vi tu ultimo mensaje en el otro tema :-(
casualmente mientras me escribias este ultimo mensaje, estaba implementandolo con estructuras como sugerias en el otro tema. Y ya llama bien a al metodo warshall, pero creo devuelve mal los valores. Es que no me aclaro mucho con el metodo. Lo he tenido que modificar, porque si le implementaba tal como estaba, como le puedo asignar a una matriz de tipo bool, una matriz de tipo int que es donde van concatenadas las ciudades asignadas por una numeracion?. A mi me da como resultado la tabla con todos 1, supongo que no esta bien.
En la tabla que compartes, el 0 es la ciudad actual, el -1 una ciudad inalcanzable, el 1 supongo que sera una ciudad alcanzable, pero los valores 4, 5 y 6 que aparecen en la tabla que significan.
Pego el nuevo codigo por si esta muy mal lo repito, y si solo hay que retocarlo un poco lo del metodo warshall que la verdad es voy perdido como funciona, solo modifico ese metodo:
En parte ya estaban las correciones que me has comentado, revisare las otras que no estan realizadas. Pego el codigo. Muchas gracias!
Código
struct ciudades
{
char ciudad1 [maxCiudad];
char ciudad2 [maxCiudad];
int distancia;
};
/*void mas_corto(unsigned int c[][], unsigned int a[][], int P[][], unsigned int nNodos)
{
int i,j,k;
for (i = 0; i < nNodos; i++)
{
for(j=0; j < nNodos; j++)
{
// Inicializamos con el coste de los caminos directos
A[i][j] = C[i][j]; P[i][j] = -1;
}
}
for (k = 0; k < nNodos; k++)
for (i = 0; i < nNodos; i++)
for (j=0; j< nNodos; j++)
if (A[i][k]+A[k][j] < A[i][j])
{
A[i][j] = A[i][k] + A[k][j];
P[i][j] = k;
}
} */
int contar_filas(int *filas)
{
FILE *fichero;
char linea[maxLinea];
char * campo;
fichero= fopen( "carreteras.txt", "r");
if(fichero==NULL)
{
printf("No se ha podido abrir el fichero.\n");
exit(1);
}
else
{
while(fgets(linea,maxLinea,fichero))
{
(*filas)++;
}
}
fclose(fichero);
return (*filas);
}
void warshall (int **A, unsigned int nNodos)
{
int i,j,k;
for (k = 0; k < nNodos; k++)
for (i = 0; i < nNodos; i++)
for (j=0; j< nNodos; j++)
A[i][j] = A[i][j] || A[i][k] && A[k][j]; //Si hay un camino de ‘i’ a ‘j’ o si hay //un camino de ‘i’ a ‘j’ pasando por ‘k’
for (int i=0; i<nNodos; i++)
{
for (int j=0; j<nNodos; j++)
printf("%d ",A[i][j]);
printf("\n");
}
}
int main()
{
FILE *fichero;
struct ciudades *city;
int *filas=0, *columnas=0, clave=1;
int cont=0, rows;
char ciudad1[maxCiudad];
char ciudad2[maxCiudad];
char distancia[maxCiudad];
int **claves;
fichero= fopen( "carreteras.txt", "r");
if(fichero==NULL)
{
printf("No se ha podido abrir el fichero.\n");
exit(1);
}
else
{
filas=contar_filas(&filas);
rows=filas;
city=malloc(rows*sizeof(struct ciudades));
claves=malloc(rows*sizeof(int*));
for(int i=0; i<rows; i++)
{
claves[i]=malloc(2*sizeof(int));
}
// se lee cada fila de todo el fichero de elementos
while(fscanf(fichero, "%s %s %s", ciudad1, ciudad2, distancia) == 3)
{
strcpy(city[cont].ciudad1,ciudad1);
strcpy(city[cont].ciudad2,ciudad2);
city[cont].distancia=ciudad2;
cont++;
}
}
for(int i=0; i<rows; i++)
{
for(int j=0; j<2; j++)
{
if(strcmp(city[i].ciudad1,"Corunya")==0)
claves[i][j]=1;
if(strcmp(city[i].ciudad2,"Corunya")==0)
claves[i][j]=1;
if(strcmp(city[i].ciudad1,"Vigo")==0)
claves[i][j]=2;
if(strcmp(city[i].ciudad2,"Vigo")==0)
claves[i][j]=2;
if(strcmp(city[i].ciudad1,"Valladolid")==0)
claves[i][j]=3;
if(strcmp(city[i].ciudad2,"Valladolid")==0)
claves[i][j]=3;
if(strcmp(city[i].ciudad1,"Bilbao")==0)
claves[i][j]=4;
if(strcmp(city[i].ciudad2,"Bilbao")==0)
claves[i][j]=4;
if(strcmp(city[i].ciudad1,"Madrid")==0)
claves[i][j]=5;
if(strcmp(city[i].ciudad2,"Madrid")==0)
claves[i][j]=5;
if(strcmp(city[i].ciudad1,"Zaragoza")==0)
claves[i][j]=7;
if(strcmp(city[i].ciudad2,"Zaragoza")==0)
claves[i][j]=7;
if(strcmp(city[i].ciudad1,"Barcelona")==0)
claves[i][j]=8;
if(strcmp(city[i].ciudad2,"Barcelona")==0)
claves[i][j]=8;
if(strcmp(city[i].ciudad1,"Gerona")==0)
claves[i][j]=9;
if(strcmp(city[i].ciudad2,"Gerona")==0)
claves[i][j]=9;
if(strcmp(city[i].ciudad1,"Valencia")==0)
claves[i][j]=10;
if(strcmp(city[i].ciudad2,"Valencia")==0)
claves[i][j]=10;
if(strcmp(city[i].ciudad1,"Badajoz")==0)
claves[i][j]=11;
if(strcmp(city[i].ciudad2,"Badajoz")==0)
claves[i][j]=11;
if(strcmp(city[i].ciudad1,"Jaen")==0)
claves[i][j]=12;
if(strcmp(city[i].ciudad2,"Jaen")==0)
claves[i][j]=12;
if(strcmp(city[i].ciudad1,"Albacete")==0)
claves[i][j]=13;
if(strcmp(city[i].ciudad2,"Albacete")==0)
claves[i][j]=13;
if(strcmp(city[i].ciudad1,"Murcia")==0)
claves[i][j]=14;
if(strcmp(city[i].ciudad2,"Murcia")==0)
claves[i][j]=14;
if(strcmp(city[i].ciudad1,"Granada")==0)
claves[i][j]=15;
if(strcmp(city[i].ciudad2,"Granada")==0)
claves[i][j]=15;
if(strcmp(city[i].ciudad1,"Sevilla")==0)
claves[i][j]=16;
if(strcmp(city[i].ciudad2,"Sevilla")==0)
claves[i][j]=16;
if(strcmp(city[i].ciudad1,"Cadiz")==0)
claves[i][j]=17;
if(strcmp(city[i].ciudad2,"Cadiz")==0)
claves[i][j]=17;
}
}
warshall(claves,n_Nodos);
return 0;
}
Y el resultado que muestra por pantalla:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Navegación
[#] Página Siguiente