Computing All-Pairs Shortest Paths with the Floyd-Warshall Algorithm

In graph theory and network routing, determining the shortest path between interconnected nodes is a fundamental challenge. Algorithms like Dijkstra or Bellman-Ford excel when querying paths from a single origin node to all other reachable destinations. However, peer-to-peer mesh networks, flight pricing engines, transit networks, and distributed service mesh latency matrices frequently require knowing the shortest distance between every possible pair of vertices simultaneously. While running Dijkstra from every vertex works on sparse graphs with strictly non-negative edge weights, dense graphs or networks containing negative cost adjustments benefit from a centralized, matrix-based dynamic programming approach.

The Floyd-Warshall algorithm resolves the all-pairs shortest path (APSP) problem through an elegant recurrence relation. By systematically testing every vertex as a potential intermediate stepping stone, the algorithm evaluates whether routing from a source vertex $i$ to a destination vertex $j$ through an intermediate vertex $k$ reduces the current path cost. Operating in $O(V^3)$ time and $O(V^2)$ space across an adjacency matrix, Floyd-Warshall handles graphs with negative edge weights, detects negative cycles when any diagonal distance $\text{dist}[i][i]$ falls below zero, and tracks an auxiliary transition matrix that enables full path reconstruction between any two points in the network.

Example #

// Minimal 3-node graph distance matrix
const INF = Infinity;
const dist = [
  [0,   4,   INF],
  [INF, 0,   1  ],
  [2,   INF, 0  ]
];
const n = dist.length;

// Core dynamic programming relaxation
for (let k = 0; k < n; k++) {
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (dist[i][k] + dist[k][j] < dist[i][j]) {
        dist[i][j] = dist[i][k] + dist[k][j];
      }
    }
  }
}

console.log('Shortest distance 0 -> 2:', dist[0][2]); // 5 (via 0 -> 1 -> 2)

Implementation #

/**
 * Floyd-Warshall All-Pairs Shortest Path Implementation
 * Supports directed/undirected weighted graphs, negative edge weights,
 * negative cycle detection, and complete path reconstruction.
 */

class AllPairsShortestPath {
  /**
   * Computes all-pairs shortest paths given an array of vertex names and edge definitions.
   * Edge format: { from: 'A', to: 'B', weight: 5 }
   */
  static compute(vertices, edges, isDirected = true) {
    const vCount = vertices.length;
    const vertexToIndex = new Map(vertices.map((v, idx) => [v, idx]));
    const indexToVertex = [...vertices];

    // Initialize distance and predecessor matrices
    const distances = Array.from({ length: vCount }, () => 
      new Array(vCount).fill(Infinity)
    );
    const nextHop = Array.from({ length: vCount }, () => 
      new Array(vCount).fill(null)
    );

    // Distance to self is always zero
    for (let i = 0; i < vCount; i++) {
      distances[i][i] = 0;
      nextHop[i][i] = i;
    }

    // Populate direct edges
    for (const edge of edges) {
      const u = vertexToIndex.get(edge.from);
      const v = vertexToIndex.get(edge.to);

      if (u === undefined || v === undefined) {
        throw new Error(`Edge references unknown vertex: ${edge.from} -> ${edge.to}`);
      }

      distances[u][v] = edge.weight;
      nextHop[u][v] = v;

      if (!isDirected) {
        distances[v][u] = edge.weight;
        nextHop[v][u] = u;
      }
    }

    // Floyd-Warshall dynamic programming relaxation
    for (let k = 0; k < vCount; k++) {
      for (let i = 0; i < vCount; i++) {
        for (let j = 0; j < vCount; j++) {
          // Avoid overflow when adding Infinity
          if (distances[i][k] !== Infinity && distances[k][j] !== Infinity) {
            const combinedDist = distances[i][k] + distances[k][j];
            if (combinedDist < distances[i][j]) {
              distances[i][j] = combinedDist;
              nextHop[i][j] = nextHop[i][k];
            }
          }
        }
      }
    }

    // Detect negative cycles: any negative diagonal indicates a cycle
    for (let i = 0; i < vCount; i++) {
      if (distances[i][i] < 0) {
        return {
          hasNegativeCycle: true,
          error: `Graph contains a negative-weight cycle affecting vertex: ${indexToVertex[i]}`
        };
      }
    }

    return {
      hasNegativeCycle: false,
      distances,
      nextHop,
      vertexToIndex,
      indexToVertex,
      getPath: (from, to) => AllPairsShortestPath.reconstructPath(
        from, 
        to, 
        vertexToIndex, 
        indexToVertex, 
        distances, 
        nextHop
      )
    };
  }

  /**
   * Reconstructs the exact node sequence for the shortest path from 'from' to 'to'.
   */
  static reconstructPath(from, to, vertexMap, indexMap, distMatrix, nextMatrix) {
    const u = vertexMap.get(from);
    const v = vertexMap.get(to);

    if (u === undefined || v === undefined) {
      return null;
    }

    if (distMatrix[u][v] === Infinity) {
      return null; // Unreachable
    }

    const path = [indexMap[u]];
    let current = u;

    while (current !== v) {
      current = nextMatrix[current][v];
      if (current === null) return null;
      path.push(indexMap[current]);
    }

    return {
      path,
      totalDistance: distMatrix[u][v]
    };
  }
}

// Verification with sample server routing latency network
const nodes = ['NYC', 'LON', 'FRA', 'TOK', 'SYD'];
const links = [
  { from: 'NYC', to: 'LON', weight: 75 },
  { from: 'NYC', to: 'TOK', weight: 140 },
  { from: 'LON', to: 'FRA', weight: 20 },
  { from: 'FRA', to: 'TOK', weight: 110 },
  { from: 'TOK', to: 'SYD', weight: 95 },
  { from: 'LON', to: 'SYD', weight: 260 }
];

const result = AllPairsShortestPath.compute(nodes, links, false);

console.log('Is graph free of negative cycles?', !result.hasNegativeCycle);
console.log('Shortest route NYC -> SYD:', result.getPath('NYC', 'SYD'));
// { path: ['NYC', 'LON', 'FRA', 'TOK', 'SYD'], totalDistance: 300 }
console.log('Shortest route NYC -> FRA:', result.getPath('NYC', 'FRA'));
// { path: ['NYC', 'LON', 'FRA'], totalDistance: 95 }

Main Point: The Floyd-Warshall algorithm computes all-pairs shortest paths across dense graphs in cubic time and quadratic space using dynamic programming while detecting negative cycles and enabling path reconstruction.

Credits #

Photo by Kalen Emsley on Unsplash

← Home