Suggest an edit

Improve this article

Refine the answer for “What does the Floyd-Warshall algorithm do on graphs?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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)

```js
const INF = Infinity;

// 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

1. Keep the matrix next: next[i][j] = the first vertex after i on the shortest path to j.
2. 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.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts895 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.