Floyd-Warshall computes shortest-path distances between every pair of vertices.

Its central dynamic-programming transition is:

dist[i][j] =
min(
  dist[i][j],
  dist[i][k] + dist[k][j]
)

For each intermediate vertex k, the algorithm asks whether routing i → k → j improves the current best route from i to j.

Initialization

For every vertex:

dist[i][i] = 0

For a direct edge i → j with weight w:

dist[i][j] = w

If no path is currently known:

dist[i][j] = Infinity

JavaScript

function floydWarshall(matrix) {
  const dist = matrix.map(row => [...row]);
  const n = dist.length;

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < n; j++) {
        dist[i][j] = Math.min(
          dist[i][j],
          dist[i][k] + dist[k][j]
        );
      }
    }
  }

  return dist;
}

Why k is the outer loop

k represents the set of intermediate vertices currently allowed by the DP state.

Keeping it outermost preserves the recurrence that gradually expands the permitted intermediate set.

Negative edges

Floyd-Warshall supports negative edge weights.

The problem is not a negative edge itself, but a reachable negative cycle.

Negative-cycle detection

After the algorithm finishes, a negative diagonal entry:

dist[i][i] < 0

proves that a negative cycle exists.

Only source-destination pairs that can reach and leave such a cycle have an unbounded shortest-path value.

Path reconstruction

A second matrix:

next[i][j]

can store the first hop on the current best route.

When a shorter route through k is found:

next[i][j] = next[i][k]

This allows the actual vertex sequence to be reconstructed, not only its cost.

Transitive closure

The same triple-loop structure computes all-pairs reachability by replacing arithmetic operations with Boolean logic:

reach[i][j] =
reach[i][j]
OR
(
  reach[i][k]
  AND
  reach[k][j]
)

This is closely associated with Warshall's algorithm.

Floyd-Warshall vs Dijkstra

Floyd-Warshall:

All pairs
O(V³)

Repeated Dijkstra can be better for large sparse graphs with non-negative weights.

Floyd-Warshall is particularly attractive when the graph is moderate in size, dense, matrix-based, or queried heavily after preprocessing.

Floyd-Warshall vs Bellman-Ford

Bellman-Ford:

single source
O(VE)

Floyd-Warshall:

all pairs
O(V³)

Both can handle negative edges and detect negative-cycle behavior in different ways.

Floyd-Warshall vs Johnson

Johnson's algorithm is often preferable for sparse all-pairs graphs with negative edges but no negative cycles.

It combines Bellman-Ford reweighting with repeated Dijkstra.

Real-world use cases

• precomputed routing matrices,
• logistics between a moderate number of hubs,
• branch-to-branch cost matrices,
• network latency analysis,
• small game maps,
• all-pairs dependency costs,
• transitive closure and reachability.

Edge cases

• empty matrix,
• one vertex,
• negative self-loop,
• duplicate parallel edges,
• unreachable pairs,
• directed vs undirected initialization.

For duplicate direct edges, initialize the matrix with the minimum direct weight.

Building a matrix from edges

function buildMatrix(n, edges) {
  const dist = Array.from(
    { length: n },
    () => Array(n).fill(Infinity)
  );

  for (let i = 0; i < n; i++) {
    dist[i][i] = 0;
  }

  for (const [u, v, w] of edges) {
    dist[u][v] = Math.min(
      dist[u][v],
      w
    );
  }

  return dist;
}

TypeScript

type DistanceMatrix = number[][];

function floydWarshall(
  matrix: DistanceMatrix
): DistanceMatrix {
  const dist = matrix.map(
    row => [...row]
  );

  const n = dist.length;

  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      if (dist[i][k] === Infinity) continue;

      for (let j = 0; j < n; j++) {
        if (dist[k][j] === Infinity) continue;

        const candidate =
          dist[i][k] + dist[k][j];

        if (candidate < dist[i][j]) {
          dist[i][j] = candidate;
        }
      }
    }
  }

  return dist;
}

Complexity

Time:  O(V³)
Space: O(V²)

The output itself is a V × V matrix, so quadratic space is inherent when all pairwise distances must be stored.

Common mistakes

• setting missing edges to zero instead of Infinity,
• forgetting zero diagonal initialization,
• changing loop roles without understanding the DP state,
• ignoring negative-cycle detection,
• using Floyd-Warshall for a huge sparse graph,
• keeping only distances when actual paths are required.

Summary

Floyd-Warshall is a compact dynamic-programming solution for all-pairs shortest paths.

Use it when:

all-pairs distances are required
+ V is moderate
+ O(V³) is acceptable

It also generalizes naturally to path reconstruction and transitive closure.