Floyd Warshall Algorithm All-Pairs Shortest Path

Problem Statement❯

The Floyd Warshall Algorithm solves the problem of finding the shortest path between all pairs of vertices in a weighted, directed graph.

The graph is given as an n × n adjacency matrix matrix, where matrix[i][j] represents the weight of the edge from node i to node j. A value of -1 indicates that there is no direct edge between the two nodes.

Your task is to compute the shortest distances between every pair of nodes. If there is no path between two nodes, the corresponding distance should remain -1.

Examples❯

Input Matrix	Output Matrix	Description
[[0, 3, -1], [-1, 0, 1], [4, -1, 0]]	[[0, 3, 4], [5, 0, 1], [4, 7, 0]]	Shortest paths computed between all vertex pairs
[[0, 5, -1], [-1, 0, 2], [3, -1, 0]]	[[0, 5, 7], [5, 0, 2], [3, 8, 0]]	Path from 0 to 2 via 1 with weight 5+2=7
[[0, -1, -1], [-1, 0, -1], [-1, -1, 0]]	[[0, -1, -1], [-1, 0, -1], [-1, -1, 0]]	No edges means no shorter paths can be found

Solution❯

The Floyd Warshall Algorithm is a classic dynamic programming approach that helps compute the shortest distances between all pairs of vertices in a graph.

The core idea is to consider every node as an intermediate node and check if the path from i to j through k is shorter than the current known distance. If it is, we update the distance.

To handle the -1 values that represent no edge, we treat them as infinity during calculations and later convert them back to -1 if no path was found.

The algorithm runs in O(n³) time and is best suited for dense graphs or when we need all-pairs shortest paths.

Algorithm Steps❯

Let matrix be the input adjacency matrix of size n × n.
Initialize a distance matrix dist with the same values as matrix.
Replace all -1 values (except diagonals) in dist with Infinity.
For each node k from 0 to n-1:

For each node i from 0 to n-1:
For each node j from 0 to n-1:
If dist[i][k] + dist[k][j] < dist[i][j], update dist[i][j].

Convert all Infinity values in dist back to -1.

Code

JavaScript

function floydWarshall(matrix) {
  const n = matrix.length;
  const dist = Array.from({ length: n }, (_, i) =>
    matrix[i].map(val => (val === -1 && i !== matrix[i].indexOf(val) ? Infinity : val))
  );

  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] !== Infinity && dist[k][j] !== Infinity) {
          dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
        }
      }
    }
  }

  // Convert Infinity back to -1
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (dist[i][j] === Infinity) dist[i][j] = -1;
    }
  }

  return dist;
}

const matrix = [
  [0, 3, -1],
  [-1, 0, 1],
  [4, -1, 0]
];

console.log("Shortest distances:", floydWarshall(matrix));

⬅ Previous TopicBellman-Ford Algorithm for Shortest Paths

Next Topic ⮕Find the City With the Fewest Reachable Neighbours