SimuVedaAlgorithms Lab Open in the lab

Graphs / Advanced

Floyd-Warshall All-Pairs Shortest Paths Visualizer

Allow one more node k as a stopover at a time. For every pair (i, j), going i → k → j might beat the best path found so far. After every k has been tried, all distances are final.

Start the Floyd-Warshall All-Pairs Shortest Paths simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(V³)
Average timeO(V³)
Worst timeO(V³)
Extra spaceO(V²)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Start with direct edges only. ∞ means no direct edge yet.
  2. k = A: may paths now stop over at A? Row and column A are what we read.
  3. k = B: may paths now stop over at B? Row and column B are what we read.
  4. A → B → C costs 3 + 2 = 5, better than 8. Update.
  5. A → B → D costs 3 + 5 = 8, better than ∞. Update.
  6. C → B → A costs 2 + 3 = 5, better than 8. Update.
  7. D → B → A costs 5 + 3 = 8, better than ∞. Update.
  8. k = C: may paths now stop over at C? Row and column C are what we read.
  9. A → C → D costs 5 + 1 = 6, better than 8. Update.
  10. A → C → E costs 5 + 9 = 14, better than ∞. Update.
  11. B → C → D costs 2 + 1 = 3, better than 5. Update.
  12. B → C → E costs 2 + 9 = 11, better than ∞. Update.
  13. D → C → A costs 1 + 5 = 6, better than 8. Update.
  14. D → C → B costs 1 + 2 = 3, better than 5. Update.
  15. E → C → A costs 9 + 5 = 14, better than ∞. Update.
  16. E → C → B costs 9 + 2 = 11, better than ∞. Update.
  17. k = D: may paths now stop over at D? Row and column D are what we read.
  18. A → D → E costs 6 + 4 = 10, better than 14. Update.
  19. B → D → E costs 3 + 4 = 7, better than 11. Update.
  20. C → D → E costs 1 + 4 = 5, better than 9. Update.
  21. … 1 more steps …
  22. E → D → B costs 4 + 3 = 7, better than 11. Update.
  23. E → D → C costs 4 + 1 = 5, better than 9. Update.
  24. k = E: may paths now stop over at E? Row and column E are what we read.
  25. Done after 5 rounds. Every cell is now the shortest distance between its row and column node.

Try it with your own input →

Floyd-Warshall all-pairs shortest paths in Java, Python, C++, C and JavaScript

void floydWarshall(int[][] d) {
  int n = d.length;
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (d[i][k] + d[k][j] < d[i][j])
          d[i][j] = d[i][k] + d[k][j];
}
def floyd_warshall(d):
    n = len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if d[i][k] + d[k][j] < d[i][j]:
                    d[i][j] = d[i][k] + d[k][j]
void floydWarshall(vector<vector<int>>& d) {
  int n = d.size();
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (d[i][k] + d[k][j] < d[i][j])
          d[i][j] = d[i][k] + d[k][j];
}
#define MAXN 100

void floydWarshall(int n, int d[MAXN][MAXN]) {
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (d[i][k] + d[k][j] < d[i][j])
          d[i][j] = d[i][k] + d[k][j];
}
function floydWarshall(d) {
  const n = d.length;
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (d[i][k] + d[k][j] < d[i][j])
          d[i][j] = d[i][k] + d[k][j];
}

In an interview

LeetCode 1334, Find the City With the Smallest Number of Neighbors at a Threshold Distance. Also 399 Evaluate Division and transitive closure.

The k loop must be the outer loop. Swapping the loop order is the classic bug. Negative edges are fine in a directed graph; a negative d[i][i] reveals a negative cycle.

More graphs