Last Updated: September 12, 2021
·
69
· Bruno Volpato

Floyd-Warshall algorithm in Java

Floyd-Warshall is simple to implement, but complexity is O(V^3) so need to be careful when using it.

Given a distance matrix D:

// Floyd-Warshall Algorithm
for (int k = 0; k < n; k++) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (D[i][j] > D[i][k] + D[k][j]) {
        D[i][j] = D[i][k] + D[k][j];
      }
    }
  }
}

Distance from s to t becomes D[s][t]