All Pairs Shortest Paths (Dynamic Programming Algorithm)

 // Input: Weight matrix
 double[][] w = g.getAdjacencyMatrix();

 // d(k)(i,j) = Shortest path from i to j using {1..k} vertices as
 // intermediate vertices.
 double[][][] d = new double[n + 1][n][n];
 // p[i,j] = The first hop in the shortest path from i to j
 // To deduce the full path from node 2 to node 17, we can compute:
 // p[2][17], p[p[2][17]][17], etc.
 int[][] p = new int[n][n];

 // Initialize d(0)(i,j) = w(i,j) and p(i,j) = j. (Direct paths)
 for (int i = 0; i < n; i++) {
   for (int j = 0; j < n; j++) {
     d[0][i][j] = w[i][j];
     p[i][j] = j;
   }
 }
 
 // Dynamic Programming Recursive step
 // Not a recursive call per se, but
 // d(k)(i,j) = min{d(k-1)(i,j), d(k-1)(i,k) + d(k-1)(k,j)}
 for (int k = 1; k <= n; k++) {
   int x = k - 1;
   for (int i = 0; i < n; i++) {
     for (int j = 0; j < n; j++) {
       if (d[k - 1][i][j] <= d[k - 1][i][x] + d[k - 1][x][j]) {
         d[k][i][j] = d[k - 1][i][j];
       } else {
         d[k][i][j] = d[k - 1][i][x] + d[k - 1][x][j];
         p[i][j] = p[i][x];
       }
     }
   }
 }
 
 // Print out the shortest path distances
 for (int i = 0; i < n; i++) {
   for (int j = 0; j < n; j++) {
     System.out.println("d[" + i + "," + j + "]: " + d[n - 1][i][j]);
   }
 }
 
 // Print out the shortest paths (just the first vertices)
 for (int i = 0; i < n; i++) {
   for (int j = 0; j < n; j++) {
     System.out.println("p[" + i + "," + j + "]: " + p[i][j]);
   }
 }