jsschools

Floyd-Warshall Algorithm

Computes shortest paths between all pairs of vertices in a weighted graph using dynamic programming; handles negative weights but not negative cycles.

Spec ↗

Syntax

floydWarshall(W)

Parameters

NameTypeRequiredDescription
W number[][] Yes V×V weight matrix where W[i][j] is the direct edge weight from i to j, Infinity if no direct edge, and 0 on the diagonal.

Returns

number[][] | null — V×V distance matrix, or null if a negative cycle is detected.

Examples

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

  for (let k = 0; k < V; k++)
    for (let i = 0; i < V; i++)
      for (let j = 0; j < V; j++)
        if (dist[i][k] + dist[k][j] < dist[i][j])
          dist[i][j] = dist[i][k] + dist[k][j];

  // Negative cycle check: any dist[i][i] < 0
  for (let i = 0; i < V; i++) if (dist[i][i] < 0) return null;
  return dist;
}

const INF = Infinity;
const W = [
  [0, 3, INF, 7],
  [8, 0, 2, INF],
  [5, INF, 0, 1],
  [2, INF, INF, 0],
];
const result = floydWarshall(W);
console.log(result[0]); // shortest from node 0 to all
Output 
[ 0, 3, 5, 6 ]

// Transitive closure (can reach?)
function transitiveClosure(adj) {
  const V = adj.length;
  const reach = adj.map(row => [...row]);
  for (let k = 0; k < V; k++)
    for (let i = 0; i < V; i++)
      for (let j = 0; j < V; j++)
        reach[i][j] ||= reach[i][k] && reach[k][j];
  return reach;
}

const adj = [[1,1,0,0],[0,1,1,0],[0,0,1,1],[0,0,0,1]];
console.log(transitiveClosure(adj)[0]); // can 0 reach each?
Output 
[ 1, 1, 1, 1 ]

Notes

| Case | Time | Space | |---------|--------|--------| | Best | O(V³) | O(V²) | | Average | O(V³) | O(V²) | | Worst | O(V³) | O(V²) | Floyd-Warshall is practical up to V ≈ 500 (500³ = 125M operations). For large sparse graphs, run Dijkstra from each vertex instead (Johnson's algorithm). The algorithm works with negative edges as long as there are no negative cycles. It can also compute transitive closure by replacing addition/min with OR/AND. Path reconstruction requires storing a predecessor matrix alongside the distance matrix.

See also