What does the Floyd-Warshall algorithm do on graphs?

AlgorithmsJunior~3 min read

Short answer

The Floyd-Warshall algorithm computes the shortest paths between all pairs of vertices in a weighted directed graph (including negative edge weights, but without negative cycles). It returns a matrix of shortest distances, can reconstruct the paths themselves, and lets you detect negative cycles (dist[i][i] < 0). Complexity: O(V^3) in time and O(V^2) in memory.

Detailed explanation

Idea of the algorithm

Dynamic programming: intermediate vertices {0..k} are gradually allowed, improving the known distances for every pair (i, j).
Main relaxation: if dist[i][k] + dist[k][j] < dist[i][j], update dist[i][j] and remember the direction for path reconstruction.
Negative cycles are detected by the condition dist[v][v] < 0 for at least one vertex v.

Input data and conventions

The graph is stored as an adjacency matrix: adj[i][j] is the weight of edge i → j, Infinity if there is no edge, 0 on the diagonal.
Negative edge weights are supported, but the algorithm is correct only when there are no negative cycles reachable from i to j.
For an undirected graph, weights are symmetrized: adj[u][v] = adj[v][u] = w.

Pseudocode

text

dist = adj (copy the matrix)
next[i][j] = j, if edge i→j exists, otherwise null
for k in [0..n-1]:
  for i in [0..n-1]:
    for j in [0..n-1]:
      if dist[i][k] + dist[k][j] < dist[i][j]:
        dist[i][j] = dist[i][k] + dist[k][j]
        next[i][j] = next[i][k]

hasNegativeCycle = exists v: dist[v][v] < 0
reconstructPath(u, v): walk next[u][v] until reaching v

Implementation in JavaScript (with path reconstruction and cycle checking)

const INF = Infinity;

function floydWarshall(adj) {
  const n = adj.length;
  const dist = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => adj[i][j]));
  const next = Array.from({ length: n }, () => Array(n).fill(null));

  // Initialization
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i === j && dist[i][j] !== 0) dist[i][j] = 0;
      if (i !== j && dist[i][j] !== INF) next[i][j] = j;
    }
  }

  // Main triple loop
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      const dik = dist[i][k];
      if (dik === INF) continue;
      for (let j = 0; j < n; j++) {
        const dkj = dist[k][j];
        if (dkj === INF) continue;
        const alt = dik + dkj;
        if (alt < dist[i][j]) {
          dist[i][j] = alt;
          next[i][j] = next[i][k];
        }
      }
    }
  }

  // Detecting negative cycles
  let hasNegativeCycle = false;
  const negativeCycleVertices = [];
  for (let v = 0; v < n; v++) {
    if (dist[v][v] < 0) {
      hasNegativeCycle = true;
      negativeCycleVertices.push(v);
    }
  }

  function reconstructPath(u, v) {
    if (next[u][v] == null) return null; // no path
    const path = [u];
    while (u !== v) {
      u = next[u][v];
      if (u == null) return null; // guard against inconsistent data
      path.push(u);
    }
    return path;
  }

  return { dist, next, hasNegativeCycle, negativeCycleVertices, reconstructPath };
}

// Example usage
// Vertices: 0,1,2,3
// Edges: 0→1(3), 0→2(8), 1→2(2), 1→3(5), 2→3(1), 3→1(-2)
const adj = [
  [0,   3,   8,   INF],
  [INF, 0,   2,   5   ],
  [INF, INF, 0,   1   ],
  [INF,-2,   INF, 0   ],
];

const { dist, reconstructPath, hasNegativeCycle } = floydWarshall(adj);
console.log('hasNegativeCycle:', hasNegativeCycle); // false
console.log('dist matrix:');
console.table(dist);

const path03 = reconstructPath(0, 3); // expected: [0,1,2,3]
console.log('path 0→3:', path03);

Result for the example (shortest distances)

text

[
  [   0,  3, 5, 6],
  [ INF,  0, 2, 3],
  [ INF, -1, 0, 1],
  [ INF, -2, 0, 0]
]
// Path 0→3: 0 → 1 → 2 → 3, weight 6

Detecting negative cycles

If, after running the algorithm, a vertex v is found with dist[v][v] < 0, that means a negative cycle reachable from v exists. In that case any paths that enter and leave this cycle have no finite minimal length (they can be decreased infinitely). In practice:

Stop path reconstruction if the route enters a subgraph reachable from a negative cycle.
Sometimes -Infinity is additionally "pushed" along edges reachable from negative cycles, to explicitly mark such distances as unboundedly small.

Complexity and when to use it

Time: O(V^3). Memory: O(V^2).
Good for dense graphs and when a result is needed for all pairs of vertices.
For sparse graphs and many path queries, Johnson's algorithm or running Dijkstra repeatedly (if there are no negative edges) is usually more efficient.

Path reconstruction

Keep the matrix next: next[i][j] = the first vertex after i on the shortest path to j.
Start with u, while u != v: u = next[u][v], adding vertices to the list.

Relation to Warshall's algorithm (transitive closure)

If boolean values (whether a path exists) are used instead of numbers, you get Warshall's algorithm for transitive closure: reach[i][j] |= reach[i][k] && reach[k][j]. It is the same triple-loop pattern.

Frequent interview questions

Does it support negative weights? Yes. Negative cycles are not supported (they can only be detected).
What does it return? The dist matrix of all shortest distances; optionally the next matrix for path reconstruction.
Complexity? O(V^3) time, O(V^2) memory.
When is Dijkstra better? When the graph has no negative edges and you need paths from a single vertex; for all pairs, Dijkstra is run V times or Johnson's algorithm is used.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.