Foro de elhacker.net

Programación => Programación C/C++ => Mensaje iniciado por: luar79 en 12 Mayo 2022, 11:56 am


Título: Ayuda con implementacion algoritmo warshall en C
Publicado por: luar79 en 12 Mayo 2022, 11:56 am
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
  1. void warshall (bool *c, bool *a, unsigned int nNodos)
  2. {
  3.     int i,j,k;
  4.     for (i = 0; i < nNodos; i++)
  5.         for (j=0; j< nNodos; j++)
  6.             //A[i][j] = C[i][j];
  7.             a[(i*nNodos)+j] = c[(i*nNodos)+j];
  8.  
  9.     for (k = 0; k < nNodos; k++)
  10.         for (i = 0; i < nNodos; i++)
  11.             for (j=0; j< nNodos; j++)
  12.                 //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’
  13.                 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’
  14. }
  15.  
  16.  
  17. int main()
  18. {
  19.     FILE *fichero;
  20.  
  21.     bool *a;
  22.     bool *test;
  23.     int n_Nodos=19;
  24.     char * campo;
  25.     char ** datos;
  26.     int filas=0;
  27.     int MaxLinea=maxLinea;
  28.     char lineaFinal[maxLinea];
  29.     char ciudad1[maxCiudad];
  30.     char ciudad2[maxCiudad];
  31.     char distancia[maxCiudad];
  32.     char linea[maxLinea];
  33.  
  34.  
  35.     fichero= fopen( "carreteras.txt", "r");
  36.     if(fichero==NULL)
  37.     {
  38.         printf("No se ha podido abrir el fichero.\n");
  39.         exit(1);
  40.     }
  41.  
  42.     else
  43.     {
  44.  
  45.         while(fgets(linea,MaxLinea,fichero))
  46.         {
  47.             filas++;
  48.         }
  49.  
  50.         printf("%d\n",filas);
  51.  
  52.         fichero= fopen( "carreteras.txt", "r");
  53.         datos=malloc(sizeof(char*)*filas);
  54.         datos=malloc(sizeof(char)*3);
  55.  
  56.         // se lee cada fila de todo el fichero de elementos
  57.         while(fscanf(fichero, "%s %s %s", ciudad1, ciudad2, distancia) == 3)
  58.         {
  59.             datos[filas][0]=ciudad1;
  60.             printf("El valor de la linea %s \n", ciudad1);
  61.  
  62.             datos[filas][1]=ciudad2;
  63.             printf("El valor de la linea %s \n", ciudad2);
  64.  
  65.             datos[filas][2]=distancia;
  66.             printf("El valor de la linea %s \n", distancia);
  67.  
  68.         }
  69.     }
  70.     getchar();
  71.  
  72.     a = (bool *)malloc(sizeof(bool)*(n_Nodos * n_Nodos));
  73.     // aqui no tengo claro si se recoge asi los resultados del algoritmo
  74.     int resul[filas][3]=warshall (a,datos,n_Nodos);
  75.  
  76.  
  77.     return 0;
  78. }
  79.  

Muchas gracias por la ayuda!

Título: Re: Ayuda con implementacion algoritmo warshall en C
Publicado por: MAFUS en 12 Mayo 2022, 14:04 pm
Pasa por aquí una copia del archivo de texto que usas.

Título: Re: Ayuda con implementacion algoritmo warshall en C
Publicado por: luar79 en 12 Mayo 2022, 14:27 pm
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

Título: Re: Ayuda con implementacion algoritmo warshall en C
Publicado por: K-YreX en 12 Mayo 2022, 22:37 pm
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
  1. 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:

Título: Re: Ayuda con implementacion algoritmo warshall en C
Publicado por: luar79 en 13 Mayo 2022, 00:04 am
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
  1. struct ciudades
  2. {
  3.     char ciudad1 [maxCiudad];
  4.     char ciudad2 [maxCiudad];
  5.     int distancia;
  6. };
  7.  
  8. /*void mas_corto(unsigned int c[][], unsigned int a[][], int P[][], unsigned int nNodos)
  9. {
  10.     int i,j,k;
  11.     for (i = 0; i < nNodos; i++)
  12.     {
  13.             for(j=0; j < nNodos; j++)
  14.             {
  15.                 // Inicializamos con el coste de los caminos directos
  16.                 A[i][j] = C[i][j]; P[i][j] = -1;
  17.             }
  18.     }
  19.     for (k = 0; k < nNodos; k++)
  20.         for (i = 0; i < nNodos; i++)
  21.             for (j=0; j< nNodos; j++)
  22.                 if (A[i][k]+A[k][j] < A[i][j])
  23.                 {
  24.                     A[i][j] = A[i][k] + A[k][j];
  25.                     P[i][j] = k;
  26.                 }
  27. } */
  28.  
  29. int contar_filas(int *filas)
  30. {
  31.     FILE *fichero;
  32.     char linea[maxLinea];
  33.     char * campo;
  34.  
  35.     fichero= fopen( "carreteras.txt", "r");
  36.     if(fichero==NULL)
  37.     {
  38.         printf("No se ha podido abrir el fichero.\n");
  39.         exit(1);
  40.     }
  41.     else
  42.     {
  43.         while(fgets(linea,maxLinea,fichero))
  44.         {
  45.             (*filas)++;
  46.         }
  47.     }
  48.     fclose(fichero);
  49.     return (*filas);
  50. }
  51.  
  52. void warshall (int **A, unsigned int nNodos)
  53. {
  54.     int i,j,k;
  55.  
  56.     for (k = 0; k < nNodos; k++)
  57.         for (i = 0; i < nNodos; i++)
  58.             for (j=0; j< nNodos; j++)
  59.                 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’
  60.  
  61.     for (int i=0; i<nNodos; i++)
  62.     {
  63.         for (int j=0; j<nNodos; j++)
  64.             printf("%d ",A[i][j]);
  65.         printf("\n");
  66.     }
  67. }
  68.  
  69. int main()
  70. {
  71.     FILE *fichero;
  72.     struct  ciudades *city;
  73.     int *filas=0, *columnas=0, clave=1;
  74.     int cont=0, rows;
  75.     char ciudad1[maxCiudad];
  76.     char ciudad2[maxCiudad];
  77.     char distancia[maxCiudad];
  78.     int **claves;
  79.  
  80.     fichero= fopen( "carreteras.txt", "r");
  81.     if(fichero==NULL)
  82.     {
  83.         printf("No se ha podido abrir el fichero.\n");
  84.         exit(1);
  85.     }
  86.     else
  87.     {
  88.         filas=contar_filas(&filas);
  89.         rows=filas;
  90.  
  91.         city=malloc(rows*sizeof(struct ciudades));
  92.         claves=malloc(rows*sizeof(int*));
  93.         for(int i=0; i<rows; i++)
  94.         {
  95.             claves[i]=malloc(2*sizeof(int));
  96.         }
  97.  
  98.         // se lee cada fila de todo el fichero de elementos
  99.         while(fscanf(fichero, "%s %s %s", ciudad1, ciudad2, distancia) == 3)
  100.         {
  101.             strcpy(city[cont].ciudad1,ciudad1);
  102.             strcpy(city[cont].ciudad2,ciudad2);
  103.             city[cont].distancia=ciudad2;
  104.             cont++;
  105.         }
  106.     }
  107.  
  108.     for(int i=0; i<rows; i++)
  109.     {
  110.         for(int j=0; j<2; j++)
  111.         {
  112.  
  113.             if(strcmp(city[i].ciudad1,"Corunya")==0)
  114.                 claves[i][j]=1;
  115.             if(strcmp(city[i].ciudad2,"Corunya")==0)
  116.                 claves[i][j]=1;
  117.  
  118.             if(strcmp(city[i].ciudad1,"Vigo")==0)
  119.                 claves[i][j]=2;
  120.             if(strcmp(city[i].ciudad2,"Vigo")==0)
  121.                 claves[i][j]=2;
  122.  
  123.             if(strcmp(city[i].ciudad1,"Valladolid")==0)
  124.                 claves[i][j]=3;
  125.             if(strcmp(city[i].ciudad2,"Valladolid")==0)
  126.                 claves[i][j]=3;
  127.  
  128.             if(strcmp(city[i].ciudad1,"Bilbao")==0)
  129.                 claves[i][j]=4;
  130.             if(strcmp(city[i].ciudad2,"Bilbao")==0)
  131.                 claves[i][j]=4;
  132.  
  133.             if(strcmp(city[i].ciudad1,"Madrid")==0)
  134.                 claves[i][j]=5;
  135.             if(strcmp(city[i].ciudad2,"Madrid")==0)
  136.                 claves[i][j]=5;
  137.  
  138.             if(strcmp(city[i].ciudad1,"Zaragoza")==0)
  139.                 claves[i][j]=7;
  140.             if(strcmp(city[i].ciudad2,"Zaragoza")==0)
  141.                 claves[i][j]=7;
  142.  
  143.             if(strcmp(city[i].ciudad1,"Barcelona")==0)
  144.                 claves[i][j]=8;
  145.             if(strcmp(city[i].ciudad2,"Barcelona")==0)
  146.                 claves[i][j]=8;
  147.  
  148.             if(strcmp(city[i].ciudad1,"Gerona")==0)
  149.                 claves[i][j]=9;
  150.             if(strcmp(city[i].ciudad2,"Gerona")==0)
  151.                 claves[i][j]=9;
  152.             if(strcmp(city[i].ciudad1,"Valencia")==0)
  153.                 claves[i][j]=10;
  154.             if(strcmp(city[i].ciudad2,"Valencia")==0)
  155.                 claves[i][j]=10;
  156.  
  157.             if(strcmp(city[i].ciudad1,"Badajoz")==0)
  158.                 claves[i][j]=11;
  159.             if(strcmp(city[i].ciudad2,"Badajoz")==0)
  160.                 claves[i][j]=11;
  161.  
  162.             if(strcmp(city[i].ciudad1,"Jaen")==0)
  163.                 claves[i][j]=12;
  164.             if(strcmp(city[i].ciudad2,"Jaen")==0)
  165.                 claves[i][j]=12;
  166.  
  167.             if(strcmp(city[i].ciudad1,"Albacete")==0)
  168.                 claves[i][j]=13;
  169.             if(strcmp(city[i].ciudad2,"Albacete")==0)
  170.                 claves[i][j]=13;
  171.  
  172.             if(strcmp(city[i].ciudad1,"Murcia")==0)
  173.                 claves[i][j]=14;
  174.             if(strcmp(city[i].ciudad2,"Murcia")==0)
  175.                 claves[i][j]=14;
  176.  
  177.             if(strcmp(city[i].ciudad1,"Granada")==0)
  178.                 claves[i][j]=15;
  179.             if(strcmp(city[i].ciudad2,"Granada")==0)
  180.                 claves[i][j]=15;
  181.  
  182.             if(strcmp(city[i].ciudad1,"Sevilla")==0)
  183.                 claves[i][j]=16;
  184.             if(strcmp(city[i].ciudad2,"Sevilla")==0)
  185.                 claves[i][j]=16;
  186.  
  187.             if(strcmp(city[i].ciudad1,"Cadiz")==0)
  188.                 claves[i][j]=17;
  189.             if(strcmp(city[i].ciudad2,"Cadiz")==0)
  190.                 claves[i][j]=17;
  191.         }
  192.     }
  193.  
  194.     warshall(claves,n_Nodos);
  195.  
  196.     return 0;
  197. }
  198.  

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

Título: Re: Ayuda con implementacion algoritmo warshall en C
Publicado por: K-YreX en 13 Mayo 2022, 15:56 pm
Al publicar código agrega en la primera etiqueta el lenguaje para facilitar un poco más la lectura. Tal que así:
[code=c]
Aquí pones tu código
[/code]
En los anteriores posts te lo he ido agregando yo pero para futuro.  :rolleyes:
Citar
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.
El valor del elemento [X][Y] es el número de ciudades por las que tienes que moverte para llegar desde la ciudad X hasta la ciudad Y.
Es decir, cuando pone 1 significa que llegas directamente pero cuando pone 2 significa que tienes que pasar por una ciudad intermedia, y así sucesivamente...
Citar
A mi me da como resultado la tabla con todos 1, supongo que no esta bien.
Esto es un problema de concepto. El algoritmo Warshall espera/trabaja con una matriz de entrada que está compuesta por 0s y 1s. El 0 en una casilla significa que no se puede llegar del elemento X al elemento Y y el 1 que sí que se puede.
La implementación interna de la función warshall() parece correcta. El problema está en el input. La matriz que tú le estás haciendo llegar es la matriz 'claves' que no contiene la información esperada sino que contiene una serie de "índices" que has ido guardando tú en la parte final del código.

Te recomiendo empezar resolviendo el problema sin memoria dinámica ya que sí que conoces el número de ciudades y sus nombres de antemano (Solución 1 del otro tema pero más simplificada).
Realmente no necesitas una estructura para guardar cada "arista" del grafo compuesta por: {origen/ciudad1, destino/ciudad2, distancia}.
Lo que sí necesitas es una forma de poder relacionar una ciudad con un número (índice). Ahora te voy a dar una solución más sencilla que la anterior. No necesitas ni crear structs:
Puedes crear un array de cadenas y guardar todas las ciudades. El índice de cada ciudad será ni más ni menos que la posición que tiene esa ciudad en el array.
Código
  1. #define NUM_CIUDADES 17 // Necesitaras usar 'define' en vez de 'const int' para esto si utilizas memoria dinamica
  2.  
  3. int main() {
  4.   char *ciudades[NUM_CIUDADES] = {"Valladolid", "Madrid", "Barcelona", ...};
  5. }
  6.  
El orden en que definas aquí las ciudades es indiferente pero hará variar la posición de los elementos en la matriz (no sus valores).
El orden que usé en la solución mostrada antes fue: [Corunya, Vigo, Valladolid, Bilbao, Madrid, Oviedo, Zaragoza, Barcelona, Gerona, Valencia, Badajoz, Jaen, Albacete, Murcia, Granada, Sevilla, Cadiz]

Ahora teniendo los pasos anteriores, debes crearte la matriz de entrada (la que luego le pasarás a la función warshall() para que trabaje con ella)
Esta matriz contendrá 1s y 0s por lo que debería ser de tipo int (bool también es aceptable pero no deja de ser lo mismo -> 1 = true | 0 = false)
Código
  1. #define NUM_CIUDADES 17 // Necesitaras usar 'define' en vez de 'const int' para esto si utilizas memoria dinamica
  2.  
  3. int main() {
  4.   char *ciudades[NUM_CIUDADES] = {"Valladolid", "Madrid", "Barcelona", ...};
  5.   int matriz_entrada[NUM_CIUDADES][NUM_CIUDADES] = {0}; // Asi inicializas toda la matriz a 0
  6. }
De momento utiliza memoria estática y cuando lo tengas funcionando puedes agregarle la memoria dinámica.

Y ahora lo que queda es recorrer el fichero (no necesitas contar el número de filas) e ir buscando el índice correspondiente que tiene cada una de las ciudades. Una vez hayas encontado ambos índices, guardas un 1 en esa posición porque el 1 significa que puedes llegar desde la ciudad origen hasta la ciudad destino y si has encontrado ambas ciudades en una línea del fichero realmente te da igual la distancia, ya sabes que sí se puede llegar.
Código
  1. #define NUM_CIUDADES 17
  2. const int MAX_NOMBRE_CIUDAD = 20; // En esta si puedes usar 'const int' en vez de 'define'
  3.  
  4. int main() {
  5.   char *ciudades[NUM_CIUDADES] = {"Valladolid", "Madrid", "Barcelona", ...};
  6.   int matriz_entrada[NUM_CIUDADES][NUM_CIUDADES] = {0}; // Asi inicializas toda la matriz a 0
  7.  
  8.   char ciudad_origen[MAX_NOMBRE_CIUDAD];
  9.   char ciudad_destino[MAX_NOMBRE_CIUDAD];
  10.   int distancia; // Estrictamente hablando no necesitas ni guardar la distancia pero bueno, tampoco hacemos mal a nadie por ello
  11.  
  12.   // Otra cosa, al margen: Si al ver que el fichero no se abre, terminas la ejecucion, no necesitas despues poner un else, basta con poner el codigo seguido
  13.   FILE *fichero = fopen("loquesea.txt", "r");
  14.   if(!fichero) { // Lo mismo que decir: fichero == NULL
  15.     printf("...");
  16.     exit(1);
  17.   }
  18.  
  19.   while(fgets(fichero, "%s %s %d", ciudad_origen, ciudad_destino, &distancia) == 3) { // Recordar que 'distancia' no es un puntero -> Necesitas usar & (creo que lo olvide la otra vez)
  20.     printf("La distancia para ir de [%s] a [%s] es: %d\n", ciudad_origen, ciudad_destino, distancia); // Por si no te fias que se este leyendo bien el fichero :)
  21.     // Ahora viene la magia, necesitas saber que indices corresponden a 'ciudad_origen' y 'ciudad_destino'
  22.     int indice_origen = buscarIndice(ciudad_origen, ciudades, NUM_CIUDADES);
  23.     int indice_destino = buscarIndice(ciudad_destino, ciudades, NUM_CIUDADES);
  24.     // Ahora puedes comprobar que ambas ciudades hayan sido encontradas o confiar... cuando programas es mejor desconfiar siempre y en la vida en general :(
  25.     if(indice_origen != -1 && indice_destino != -1)
  26.       matriz_entrada[indice_origen][indice_destino] = 1; // No necesitas guardar la distancia, basta con que pongas un 1 para saber que si se puede llegar
  27.   }
  28.  
  29.   // Y ya estaria, ya tienes tu matriz_entrada con los 0s y 1s que necesita el algoritmo Warshall para trabajar
  30.   warshall(matriz_entrada, NUM_CIUDADES);
  31.  
  32.   // Y como dije, yo dejaria que la funcion warshall() solo haga los calculos y luego ya los muestras cuando quieras
  33.   for(int i = 0; i < NUM_CIUDADES; ++i) {
  34.     for(int j = 0; j < NUM_CIUDADES, ++j)
  35.       printf("%d ", matriz_entrada[i][j]);
  36.     printf("\n");
  37.   }
  38.  
  39. }

Para que el código anterior funcione correctamente te faltaría implementar las funciones:
Código
  1. // Devuelve el indice del elemento 'cadena' dentro del array 'cadenas'. Si no se encuentra, devuelve -1
  2. int buscarIndice(char *cadena, char *cadenas[], int num_cadenas);
  3.  
  4. // Reproduce el algoritmo Warshall contra la 'matriz_entrada' de orden (filas y columnas) indicado
  5. // Y por aclarar dudas, esta linea es la que te obliga a definir NUM_CIUDADES con 'define' y no con 'const int'
  6. void warshall(int matriz_entrada[][NUM_CIUDADES], int orden);

A partir de aquí ya sería agregar algunas mejoras como:
  • Utilizar memoria dinámica.
  • Que la función warshall() no modifique la matriz_entrada sino que genere otra matriz para no perder los valores iniciales.

Título: Re: Ayuda con implementacion algoritmo warshall en C
Publicado por: luar79 en 14 Mayo 2022, 18:01 pm
Muchisimas gracias! ;-)

Lo voy probando en estos dias, a ver si lo consigo dejar correctamente hecho!

Saludos!

Título: Re: Ayuda con implementacion algoritmo warshall en C
Publicado por: luar79 en 18 Mayo 2022, 01:02 am
Hola!,

he sacado un hueco para implementarlo, que voy a tope.

Y me sale este resultado:
0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1
0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
0 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 1
0 0 0 0 0 0 0 1 1 1 0 1 0 0 1 1 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0


Yo entiendo que todas las ciudades al final están conectadas unas con otras, no?. Osea desde Coruña puedes ir a Cadiz a través de las otras ciudades. Entonces no entiendo como la ultima fila da todo 0,s. Entiendo que la ultima fila es la de Cadiz en relación con las otras ciudades?. En ese caso llegando por Sevilla, hay conexión previa con las otras ciudades. No se si estaré entendiendo bien la interpretación del resultado :rolleyes:

Ahora eso si, la funcion buscar indices no se si la tengo muy afinada, porque solo me ha corrido el programa, declarando punteros como paso de variables. Adjunto el codigo:

Código
  1. #define MAX_NOMBRE_CIUDAD 40
  2. #define NUM_CIUDADES 17
  3.  
  4. int buscarIndice(char *ciudad, char *ciudades[NUM_CIUDADES], int numCiudades)
  5. {
  6.     for(int i=0; i<numCiudades; i++)
  7.     {
  8.         if(strcmp(ciudad,ciudades[i])==0)return i;
  9.     }
  10. }
  11.  
  12. void warshall(int A[][NUM_CIUDADES], int nNodos)
  13. {
  14.     int i,j,k;
  15.  
  16.     for (k = 0; k < nNodos; k++)
  17.         for (i = 0; i < nNodos; i++)
  18.             for (j=0; j< nNodos; j++)
  19.                 A[i][j] = A[i][j] || A[i][k] && A[k][j]; 
  20.  
  21. }
  22.  
  23. int main()
  24. {
  25.     char *ciudades[NUM_CIUDADES] = {"Corunya", "Vigo", "Valladolid", "Bilbao", "Madrid", "Oviedo", "Zaragoza", "Barcelona", "Gerona", "Valencia", "Badajoz", "Jaen", "Albacete", "Murcia", "Granada", "Sevilla", "Cadiz"};
  26.     int matriz_entrada[NUM_CIUDADES][NUM_CIUDADES] = {0}; 
  27.  
  28.     char ciudad_origen[MAX_NOMBRE_CIUDAD];
  29.     char ciudad_destino[MAX_NOMBRE_CIUDAD];
  30.     int distancia;
  31.  
  32.     FILE *fichero = fopen("carreteras.txt", "r");
  33.     if(!fichero)   // Lo mismo que decir: fichero == NULL
  34.     {
  35.         printf("El fichero no ha podido abrirse\n");
  36.         exit(1);
  37.     }
  38.  
  39.     while(fscanf(fichero, "%s %s %d", ciudad_origen, ciudad_destino, &distancia) == 3)  
  40.     {
  41.         printf("La distancia para ir de [%s] a [%s] es: %d\n", ciudad_origen, ciudad_destino, distancia); 
  42.  
  43.         int indice_origen = buscarIndice(ciudad_origen, ciudades, NUM_CIUDADES);
  44.         int indice_destino = buscarIndice(ciudad_destino, ciudades, NUM_CIUDADES);
  45.         if(indice_origen != -1 && indice_destino != -1)
  46.             matriz_entrada[indice_origen][indice_destino] = 1;
  47.     }
  48.  
  49.     warshall(matriz_entrada, NUM_CIUDADES);
  50.  
  51.     for(int i = 0; i < NUM_CIUDADES; ++i)
  52.     {
  53.         for(int j = 0; j < NUM_CIUDADES; ++j)
  54.             printf("%d ", matriz_entrada[i][j]);
  55.         printf("\n");
  56.     }
  57.  
  58.  
  59.     return 0;
  60. }
  61.  
  62.  

Muchas gracias de nuevo por la aclaración!

Título: Re: Ayuda con implementacion algoritmo warshall en C
Publicado por: luar79 en 18 Mayo 2022, 01:50 am
Hola de nuevo,

porque en lo que me piden en este ejercicio es comprobar que no existen ciudades aisladas o ciudades inalcanzables partiendo desde otra ciudad, y viendo a simple vista el fichero de texto, todas las ciudades estan conectadas. Entonces entiendo que deberia dar todo 1 el resultado del algoritmo no?

Gracias de nuevo!

Título: Re: Ayuda con implementacion algoritmo warshall en C
Publicado por: K-YreX en 18 Mayo 2022, 19:50 pm
Cita de: luar79 en 18 Mayo 2022, 01:50 am
Hola de nuevo,

porque en lo que me piden en este ejercicio es comprobar que no existen ciudades aisladas o ciudades inalcanzables partiendo desde otra ciudad, y viendo a simple vista el fichero de texto, todas las ciudades estan conectadas. Entonces entiendo que deberia dar todo 1 el resultado del algoritmo no?

Gracias de nuevo!
El algoritmo de Warshall trabaja con grafos dirigidos. Es decir que una conexión: A->B no implica que haya una conexión: B->A.
En el fichero de texto te dan los datos para ir de la 'ciudad_origen' a la 'ciudad_destino' pero no puedes ir en dirección contraria.
De ahí los resultados de tu matriz, que son correctos.

A Cádiz sí puedes llegar desde algunas ciudades (última columna) pero desde Cádiz no puedes ir a ninguna (última fila). Para que pudieras ir desde Cádiz a otra ciudad tendrías que tener al menos una línea del fichero que empezara por Cádiz, y no es así.

Por otro lado:
Citar
Código
  1. int buscarIndice(char *ciudad, char *ciudades[NUM_CIUDADES], int numCiudades)
  2. {
  3.     for(int i=0; i<numCiudades; i++)
  4.     {
  5.         if(strcmp(ciudad,ciudades[i])==0)return i;
  6.     }
  7. }
Está función tiene un pequeño problema... Qué pasa si no encuentras la ciudad entre todas las ciudades??
No tienes un return por defecto por lo que la comprobación que haces en el main de si los índices son distintos de -1 no tiene sentido.
Estas pequeñas cosas son las que hacen que se note que tu código es copiado... :silbar: :rolleyes:

Título: Re: Ayuda con implementacion algoritmo warshall en C
Publicado por: luar79 en 19 Mayo 2022, 00:57 am
Ok! comprendido!, estaba pensando si era por eso, si era por que va en una dirección.

Ok muchas gracias por todo!


Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines