Ejercicio de grafos en Java

[alais]

Buenos días compañeros, tengo un problemilla con un método que tengo que hacer en Java. Tengo que hacer lo siguiente:

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 [Seleccionar] Expandir


   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 [Seleccionar] Expandir

salida[i][j] = k, pongo que sea igual a k-1, pero me sigue dando la misma salida.

¿Alguien puede guiarme?

[alais]

¿Nadie?