Autor
Se pide implementar en Java un método para obtener los caminos mas cortos entre todos los pares de vértices de un grafo dirigido valorado, en el cual:
1. Los vértices del grafo contienen su número de orden 0, 1, 2, 3,..., n.
2. La matriz de adyacencias contiene el valor de las aristas.
-Si no hay arista entre dos vértices, su valor es infinito.
-Las aristas no tienen valores negativos.
Apartado a: Hacerlo para que devuelva una matriz con el número de vértices que hay en cada camino.
Apartado b: Hacerlo para que esta vez devuelva una matriz con el número de aristas de cada camino.
Bien, para el apartado a, lo que yo he hecho es esto:
Código:
public static int[][] caminosCortos(int[][] adyacentes) {
int n = adyacentes.length, infitito = Integer.MAX_VALUE;
int[][] salida = new int[adyacentes.length][adyacentes.length];
for (int i = 0; i < adyacentes.length; i++) {
for (int j = 0; j < adyacentes[i].length; j++) {
salida[i][j] = j;
}
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if ((i != j) && (adyacentes[i][k] != infitito) && (adyacentes[k][j] != infitito)) {
if (adyacentes[i][j] > (adyacentes[i][k] + adyacentes[k][j])) {
adyacentes[i][j] = adyacentes[i][k] + adyacentes[k][j];
salida[i][j] = k;
}
}
}
}
}
return salida;
}
El problema se me presenta en el b. Si bien lo único que se tiene que hacer es que devuelva uno menos que el número de vértices (si el camino mide 8 vértices, medirá 7 aristas), por mucho que cambio k, me sigue dando la misma salida
Es decir, lo que yo hago es que, en la parte de
Código:
salida[i][j] = k
¿Alguien puede guiarme?
En línea
