# All Pairs Shortest Paths (Dynamic Programming Algorithm)

// Input: Weight matrix

// 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]);
}
}