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.
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...
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.
#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)
#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.
#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
}
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
]); }
}
Para que el código anterior funcione correctamente te faltaría implementar las funciones:
// 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:
- 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.