Floyd-Warshall Algorithm

Introduction

The Floyd-Warshall algorithm finds the shortest paths between every pair of vertices in a weighted graph. Unlike Dijkstra's algorithm (which finds shortest paths from a single source), Floyd-Warshall answers the question: "What is the shortest distance from every node to every other node?" This makes it invaluable for problems involving route planning, network analysis, and transitive closure — and it works even when edges have negative weights.

The Problem It Solves

Imagine you run an airline and you have a list of direct flights between cities with their costs. A customer might ask: "What's the cheapest way to get from City A to City B?" Now imagine every customer asking that question for every possible pair of cities. You could run Dijkstra's algorithm from each city individually, but Floyd-Warshall gives you a more elegant, unified approach.

Here are real-world scenarios where Floyd-Warshall shines:

• GPS / Mapping: Precomputing the shortest route between all pairs of locations in a small city grid.
• Network Routing: Finding the lowest-latency path between all pairs of servers in a data center.
• Game Development: Precomputing movement costs between all zones on a game map.
• Social Networks: Determining the shortest "degrees of separation" between every pair of users.
• Detecting Negative Cycles: If you can go from a node to itself with a negative total cost, Floyd-Warshall can detect it.

Core Concepts

The Key Insight: Intermediate Vertices

Floyd-Warshall is built on one beautifully simple idea:

For any two vertices i and j, the shortest path between them either goes through vertex k or it doesn't.

The algorithm iterates through every possible "intermediate" vertex k and asks: "Is it cheaper to go from i to j directly, or to go from i to k and then from k to j?"

This is captured in the recurrence:

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

That's it. The entire algorithm is just this comparison, done for every combination of i, j, and k.

Think of It Like Building Bridges

Imagine a group of islands (vertices) with some direct bridges (edges) between them. Initially, you only know the distances via direct bridges. Then, one island at a time, you "open" that island as a waypoint. Each time you open an island, you check: "Does routing through this new waypoint create a shorter path between any two other islands?" After you've opened all islands as potential waypoints, you have the shortest distance between every pair.

The Distance Matrix

Floyd-Warshall operates on a 2D matrix dist[][] where dist[i][j] represents the shortest known distance from vertex i to vertex j.

Initialization:

• dist[i][i] = 0 (distance from any vertex to itself is zero)
• dist[i][j] = weight(i, j) if there's a direct edge
• dist[i][j] = Infinity if there's no direct edge

Time and Space Complexity

Aspect	Complexity
Time	O(V³) — three nested loops, each iterating over all vertices
Space	O(V²) — for the distance matrix

The cubic time complexity means Floyd-Warshall is practical for graphs with up to roughly 400–500 vertices. Beyond that, you may want to consider running Dijkstra's algorithm from each vertex instead.

Implementation

Basic Floyd-Warshall

function floydWarshall(graph) {
  const V = graph.length;
  
  // Create a copy of the adjacency matrix as our distance matrix
  const dist = [];
  for (let i = 0; i < V; i++) {
    dist[i] = [...graph[i]];
  }

  // Core algorithm: try every vertex as an intermediate waypoint
  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];
        }
      }
    }
  }

  return dist;
}

// Example usage
const INF = Infinity;

// Adjacency matrix for a 4-vertex directed graph
//     0    1    2    3
const graph = [
  [  0,   3, INF,   5],  // Vertex 0
  [  2,   0, INF,   4],  // Vertex 1
  [INF,   1,   0, INF],  // Vertex 2
  [INF, INF,   2,   0],  // Vertex 3
];

const result = floydWarshall(graph);

console.log('Shortest distances between all pairs:');
result.forEach((row, i) => {
  row.forEach((val, j) => {
    console.log(`  ${i} → ${j}: ${val === INF ? '∞' : val}`);
  });
});

Output:

Shortest distances between all pairs:
  0 → 0: 0
  0 → 1: 3
  0 → 2: 7
  0 → 3: 5
  1 → 0: 2
  1 → 1: 0
  1 → 2: 6
  1 → 3: 4
  2 → 0: 3
  2 → 1: 1
  2 → 2: 0
  2 → 3: 5
  3 → 0: 5
  3 → 1: 3
  3 → 2: 2
  3 → 3: 0

Path Reconstruction

Knowing the shortest distance is useful, but often you also need to know which path to take. We achieve this by maintaining a next matrix that tracks the next vertex on the shortest path from i to j.

function floydWarshallWithPath(graph) {
  const V = graph.length;
  const INF = Infinity;

  const dist = [];
  const next = []; // next[i][j] = the next vertex to visit from i on the way to j

  // Initialize
  for (let i = 0; i < V; i++) {
    dist[i] = [];
    next[i] = [];
    for (let j = 0; j < V; j++) {
      dist[i][j] = graph[i][j];
      if (graph[i][j] !== INF && i !== j) {
        next[i][j] = j; // Direct edge: next hop is the destination
      } else {
        next[i][j] = null;
      }
    }
    next[i][i] = i;
  }

  // Core algorithm with path tracking
  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];
          next[i][j] = next[i][k]; // To get to j, first go toward k
        }
      }
    }
  }

  return { dist, next };
}

function reconstructPath(next, start, end) {
  if (next[start][end] === null) {
    return null; // No path exists
  }

  const path = [start];
  let current = start;

  while (current !== end) {
    current = next[current][end];
    path.push(current);
  }

  return path;
}

// Example
const INF = Infinity;
const graph = [
  [  0,   3, INF,   5],
  [  2,   0, INF,   4],
  [INF,   1,   0, INF],
  [INF, INF,   2,   0],
];

const { dist, next } = floydWarshallWithPath(graph);

// Find path from vertex 0 to vertex 2
const path = reconstructPath(next, 0, 2);
console.log(`Shortest path 0 → 2: ${path.join(' → ')}`);
console.log(`Distance: ${dist[0][2]}`);
// Output: Shortest path 0 → 2: 0 → 3 → 2
// Output: Distance: 7

// Find path from vertex 2 to vertex 0
const path2 = reconstructPath(next, 2, 0);
console.log(`Shortest path 2 → 0: ${path2.join(' → ')}`);
console.log(`Distance: ${dist[2][0]}`);
// Output: Shortest path 2 → 0: 2 → 1 → 0
// Output: Distance: 3

Negative Cycle Detection

A negative cycle is a loop whose total edge weight is negative. If such a cycle exists, shortest paths are undefined (you could loop forever, reducing the distance to negative infinity). Floyd-Warshall detects this easily: after running the algorithm, if any diagonal value dist[i][i] is negative, vertex i is part of a negative cycle.

function detectNegativeCycle(graph) {
  const V = graph.length;
  const dist = [];

  for (let i = 0; i < V; i++) {
    dist[i] = [...graph[i]];
  }

  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];
        }
      }
    }
  }

  // Check for negative cycles
  const negativeCycleVertices = [];
  for (let i = 0; i < V; i++) {
    if (dist[i][i] < 0) {
      negativeCycleVertices.push(i);
    }
  }

  if (negativeCycleVertices.length > 0) {
    console.log('Negative cycle detected involving vertices:', negativeCycleVertices);
    return true;
  }

  console.log('No negative cycles found.');
  return false;
}

// Graph with a negative cycle: 1 → 2 → 3 → 1 costs 1 + (-3) + 1 = -1
const INF = Infinity;
const graphWithNegCycle = [
  [  0,   4, INF, INF],
  [INF,   0,   1, INF],
  [INF, INF,   0,  -3],
  [INF,   1, INF,   0],
];

detectNegativeCycle(graphWithNegCycle);
// Output: Negative cycle detected involving vertices: [1, 2, 3]

Transitive Closure

A variation of Floyd-Warshall can compute the transitive closure of a graph — determining whether a path exists between every pair of vertices (regardless of distance). Instead of minimizing distances, we use boolean OR operations.

function transitiveClosure(graph) {
  const V = graph.length;

  // reach[i][j] = true if there's a path from i to j
  const reach = [];
  for (let i = 0; i < V; i++) {
    reach[i] = [];
    for (let j = 0; j < V; j++) {
      reach[i][j] = graph[i][j] !== 0 && graph[i][j] !== Infinity;
    }
    reach[i][i] = true; // Every vertex can reach itself
  }

  // Floyd-Warshall variant with boolean operations
  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][j] || (reach[i][k] && reach[k][j]);
      }
    }
  }

  return reach;
}

// Adjacency: 1 means edge exists, 0 means no edge
const adjMatrix = [
  [0, 1, 0, 0],
  [0, 0, 1, 0],
  [0, 0, 0, 1],
  [0, 0, 0, 0],
];

const closure = transitiveClosure(adjMatrix);
console.log('Reachability matrix:');
closure.forEach((row, i) => {
  console.log(`  From ${i}: ${row.map((v, j) => `${j}:${v ? '✓' : '✗'}`).join('  ')}`);
});
// Vertex 0 can reach all others: 0:✓  1:✓  2:✓  3:✓
// Vertex 3 can only reach itself: 0:✗  1:✗  2:✗  3:✓

Step-by-Step Walkthrough

Let's trace through the algorithm on a small 3-vertex graph to build intuition.

Initial distance matrix:

	0	1	2
0	0	8	5
1	∞	0	1
2	3	∞	0

k = 0 (allow routing through vertex 0):

• Can 1 → 0 → 2 beat 1 → 2? ∞ + 5 = ∞ vs 1. No.
• Can 2 → 0 → 1 beat 2 → 1? 3 + 8 = 11 vs ∞. Yes! dist[2][1] = 11

k = 1 (allow routing through vertices 0, 1):

• Can 0 → 1 → 2 beat 0 → 2? 8 + 1 = 9 vs 5. No.
• Can 2 → 1 → 0 beat 2 → 0? 11 + ∞ = ∞ vs 3. No.

k = 2 (allow routing through vertices 0, 1, 2):

• Can 0 → 2 → 1 beat 0 → 1? 5 + 11 = 16 vs 8. No.
• Can 1 → 2 → 0 beat 1 → 0? 1 + 3 = 4 vs ∞. Yes! dist[1][0] = 4

Final distance matrix:

	0	1	2
0	0	8	5
1	4	0	1
2	3	11	0

Comparison with Other Shortest Path Algorithms

Algorithm	Problem Type	Negative Edges?	Time Complexity
Dijkstra	Single source	No	O(E log V)
Bellman-Ford	Single source	Yes	O(V · E)
Floyd-Warshall	All pairs	Yes	O(V³)
Johnson's	All pairs	Yes	O(V · E log V)

Why the Loop Order Matters

A common mistake is putting the k loop in the wrong position. The k loop must be the outermost loop. Here's why:

When k is the outer loop, we process intermediate vertices one at a time. By the time we consider vertex k as an intermediate, we've already computed the shortest paths using vertices 0 through k-1 as intermediates. This ensures that dist[i][k] and dist[k][j] are already optimal with respect to the first k-1 intermediates.

If you put i or j as the outermost loop, the algorithm breaks because you'd be using incomplete information.

Practical Application: City Distance Calculator

function cityDistanceCalculator() {
  const cities = ['New York', 'Chicago', 'Denver', 'Los Angeles'];
  const V = cities.length;
  const INF = Infinity;

  // Direct flight costs (or INF if no direct flight)
  const costs = [
    //  NYC   CHI   DEN    LA
    [    0,  200,  INF,  INF],  // NYC
    [  200,    0,  150,  INF],  // Chicago
    [  INF,  150,    0,  250],  // Denver
    [  INF,  INF,  250,    0],  // LA
  ];

  const { dist, next } = floydWarshallWithPath(costs);

  // Query any pair
  function findCheapestRoute(fromCity, toCity) {
    const from = cities.indexOf(fromCity);
    const to = cities.indexOf(toCity);

    if (from === -1 || to === -1) return 'City not found';
    if (dist[from][to] === INF) return 'No route available';

    const path = reconstructPath(next, from, to);
    const cityPath = path.map(i => cities[i]);

    return {
      route: cityPath.join(' → '),
      cost: dist[from][to],
    };
  }

  console.log(findCheapestRoute('New York', 'Los Angeles'));
  // { route: 'New York → Chicago → Denver → Los Angeles', cost: 600 }

  console.log(findCheapestRoute('Los Angeles', 'New York'));
  // { route: 'Los Angeles → Denver → Chicago → New York', cost: 600 }
}

cityDistanceCalculator();

Edge Cases and Gotchas

// Handling Infinity arithmetic carefully
function floydWarshallSafe(graph) {
  const V = graph.length;
  const INF = Infinity;
  const dist = graph.map(row => [...row]);

  for (let k = 0; k < V; k++) {
    for (let i = 0; i < V; i++) {
      for (let j = 0; j < V; j++) {
        // Guard against Infinity + Infinity or Infinity + negative
        if (dist[i][k] !== INF && dist[k][j] !== INF) {
          if (dist[i][k] + dist[k][j] < dist[i][j]) {
            dist[i][j] = dist[i][k] + dist[k][j];
          }
        }
      }
    }
  }

  return dist;
}

The guard dist[i][k] !== INF && dist[k][j] !== INF is important in languages where arithmetic with infinity can cause issues (e.g., integer overflow in C++ / Java). In JavaScript, Infinity + Infinity = Infinity and Infinity + (-5) = Infinity, which are mathematically correct, but adding the guard makes the intent explicit and avoids surprises.

Best Practices

1. Use Floyd-Warshall for dense, small graphs: With O(V³) complexity, it's ideal when V ≤ 500 and you need all-pairs shortest paths.
2. Always put k as the outermost loop: The correctness of the algorithm depends on processing intermediate vertices in order.
3. Guard against infinity arithmetic: Explicitly check for Infinity before adding distances, especially in statically typed languages.
4. Check for negative cycles after execution: Inspect the diagonal of the distance matrix — any dist[i][i] < 0 indicates a negative cycle.
5. Prefer in-place matrix updates: Floyd-Warshall works correctly without creating a new matrix each iteration, saving memory.
6. Use the next matrix for path reconstruction: Don't just compute distances — the path information is often equally important.
7. Consider alternatives for sparse graphs: If E << V², running Dijkstra from each vertex is often faster.
8. Initialize self-distances to zero: Forgetting dist[i][i] = 0 is a common bug that leads to incorrect results.

Related Concepts

• Dijkstra's Algorithm: Single-source shortest path for non-negative edge weights. The go-to choice when you only need paths from one starting vertex.
• Bellman-Ford Algorithm: Single-source shortest path that handles negative edges and detects negative cycles.
• Graph Representations: Understanding adjacency matrices vs. adjacency lists is foundational — Floyd-Warshall works directly on adjacency matrices.
• Dynamic Programming: Floyd-Warshall is a classic example of dynamic programming, where optimal solutions to subproblems (shorter intermediate paths) build up to the full solution.
• Breadth-First Search (BFS): For unweighted graphs, BFS solves the single-source shortest path problem in O(V + E).

Tests and Challenges

Practice Floyd-Warshall and related shortest-path concepts with these problems:

• HackerRank — Floyd: City of Blinding Lights: Direct application of Floyd-Warshall on a directed weighted graph with queries.
• LeetCode 1334 — Find the City With the Smallest Number of Neighbors at a Threshold Distance: Use Floyd-Warshall to compute all-pairs distances, then answer a query about reachability.
• LeetCode 399 — Evaluate Division: Can be modeled as a graph problem solvable with Floyd-Warshall–style transitive computation.
• LeetCode 743 — Network Delay Time: While typically solved with Dijkstra, practicing it with Floyd-Warshall builds understanding of the differences.
• LeetCode 1462 — Course Schedule IV: A transitive closure problem — a direct application of the Floyd-Warshall variant.

For deeper study, search for topics like Johnson's Algorithm (which combines Bellman-Ford with Dijkstra for all-pairs shortest paths in sparse graphs) and matrix exponentiation for shortest paths (which connects shortest-path problems to linear algebra).