Ayuda con implementacion algoritmo warshall en C
K-YreX:
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
#define NUM_CIUDADES 17 // Necesitaras usar 'define' en vez de 'const int' para esto si utilizas memoria dinamica
int main() {
char *ciudades[NUM_CIUDADES] = {"Valladolid", "Madrid", "Barcelona", ...};
}
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
#define NUM_CIUDADES 17 // Necesitaras usar 'define' en vez de 'const int' para esto si utilizas memoria dinamica
int main() {
char *ciudades[NUM_CIUDADES] = {"Valladolid", "Madrid", "Barcelona", ...};
int matriz_entrada[NUM_CIUDADES][NUM_CIUDADES] = {0}; // Asi inicializas toda la matriz a 0
}
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
#define NUM_CIUDADES 17
const int MAX_NOMBRE_CIUDAD = 20; // En esta si puedes usar 'const int' en vez de 'define'
int main() {
char *ciudades[NUM_CIUDADES] = {"Valladolid", "Madrid", "Barcelona", ...};
int matriz_entrada[NUM_CIUDADES][NUM_CIUDADES] = {0}; // Asi inicializas toda la matriz a 0
char ciudad_origen[MAX_NOMBRE_CIUDAD];
char ciudad_destino[MAX_NOMBRE_CIUDAD];
int distancia; // Estrictamente hablando no necesitas ni guardar la distancia pero bueno, tampoco hacemos mal a nadie por ello
// 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
FILE *fichero = fopen("loquesea.txt", "r");
if(!fichero) { // Lo mismo que decir: fichero == NULL
printf("...");
exit(1);
}
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)
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 :)
// Ahora viene la magia, necesitas saber que indices corresponden a 'ciudad_origen' y 'ciudad_destino'
int indice_origen = buscarIndice(ciudad_origen, ciudades, NUM_CIUDADES);
int indice_destino = buscarIndice(ciudad_destino, ciudades, NUM_CIUDADES);
// Ahora puedes comprobar que ambas ciudades hayan sido encontradas o confiar... cuando programas es mejor desconfiar siempre y en la vida en general :(
if(indice_origen != -1 && indice_destino != -1)
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
}
// Y ya estaria, ya tienes tu matriz_entrada con los 0s y 1s que necesita el algoritmo Warshall para trabajar
warshall(matriz_entrada, NUM_CIUDADES);
// Y como dije, yo dejaria que la funcion warshall() solo haga los calculos y luego ya los muestras cuando quieras
for(int i = 0; i < NUM_CIUDADES; ++i) {
for(int j = 0; j < NUM_CIUDADES, ++j)
printf("%d ", matriz_entrada[i][j]);
printf("\n");
}
}
Para que el código anterior funcione correctamente te faltaría implementar las funciones:
Código
// Devuelve el indice del elemento 'cadena' dentro del array 'cadenas'. Si no se encuentra, devuelve -1
int buscarIndice(char *cadena, char *cadenas[], int num_cadenas);
// Reproduce el algoritmo Warshall contra la 'matriz_entrada' de orden (filas y columnas) indicado
// Y por aclarar dudas, esta linea es la que te obliga a definir NUM_CIUDADES con 'define' y no con 'const int'
void warshall(int matriz_entrada[][NUM_CIUDADES], int orden);
A partir de aquí ya sería agregar algunas mejoras como:
[x] Utilizar memoria dinámica.
[x] Que la función warshall() no modifique la matriz_entrada sino que genere otra matriz para no perder los valores iniciales.
luar79:
Muchisimas gracias! ;-)
Lo voy probando en estos dias, a ver si lo consigo dejar correctamente hecho!
Saludos!
luar79:
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
#define MAX_NOMBRE_CIUDAD 40
#define NUM_CIUDADES 17
int buscarIndice(char *ciudad, char *ciudades[NUM_CIUDADES], int numCiudades)
{
for(int i=0; i<numCiudades; i++)
{
if(strcmp(ciudad,ciudades[i])==0)return i;
}
}
void warshall(int A[][NUM_CIUDADES], 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];
}
int main()
{
char *ciudades[NUM_CIUDADES] = {"Corunya", "Vigo", "Valladolid", "Bilbao", "Madrid", "Oviedo", "Zaragoza", "Barcelona", "Gerona", "Valencia", "Badajoz", "Jaen", "Albacete", "Murcia", "Granada", "Sevilla", "Cadiz"};
int matriz_entrada[NUM_CIUDADES][NUM_CIUDADES] = {0};
char ciudad_origen[MAX_NOMBRE_CIUDAD];
char ciudad_destino[MAX_NOMBRE_CIUDAD];
int distancia;
FILE *fichero = fopen("carreteras.txt", "r");
if(!fichero) // Lo mismo que decir: fichero == NULL
{
printf("El fichero no ha podido abrirse\n");
exit(1);
}
while(fscanf(fichero, "%s %s %d", ciudad_origen, ciudad_destino, &distancia) == 3)
{
printf("La distancia para ir de [%s] a [%s] es: %d\n", ciudad_origen, ciudad_destino, distancia);
int indice_origen = buscarIndice(ciudad_origen, ciudades, NUM_CIUDADES);
int indice_destino = buscarIndice(ciudad_destino, ciudades, NUM_CIUDADES);
if(indice_origen != -1 && indice_destino != -1)
matriz_entrada[indice_origen][indice_destino] = 1;
}
warshall(matriz_entrada, NUM_CIUDADES);
for(int i = 0; i < NUM_CIUDADES; ++i)
{
for(int j = 0; j < NUM_CIUDADES; ++j)
printf("%d ", matriz_entrada[i][j]);
printf("\n");
}
return 0;
}
Muchas gracias de nuevo por la aclaración!
luar79:
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!
K-YreX:
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
int buscarIndice(char *ciudad, char *ciudades[NUM_CIUDADES], int numCiudades)
{
for(int i=0; i<numCiudades; i++)
{
if(strcmp(ciudad,ciudades[i])==0)return i;
}
}
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:
Navegación
[#] Página Siguiente
[*] Página Anterior