Floyd–Warshall Algorithm

July 22, 2019 • ☕️ 3 min read

In computer science, the Floyd–Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). A single execution of the algorithm will find the lengths (summed weights) of shortest paths between all pairs of vertices. Although it does not return details of the paths themselves, it is possible to reconstruct the paths with simple modifications to the algorithm.

Algorithm

The Floyd–Warshall algorithm compares all possible paths through the graph between each pair of vertices. It is able to do this with O(|V|^3) comparisons in a graph. This is remarkable considering that there may be up to |V|^2 edges in the graph, and every combination of edges is tested. It does so by incrementally improving an estimate on the shortest path between two vertices, until the estimate is optimal.

Consider a graph G with vertices V numbered 1 through N. Further consider a function shortestPath(i, j, k) that returns the shortest possible path from i to j using vertices only from the set {1, 2, ..., k} as intermediate points along the way. Now, given this function, our goal is to find the shortest path from each i to each j using only vertices in {1, 2, ..., N}.

Recursive Formula

Recursive Formula Recursive Formula

This formula is the heart of the Floyd–Warshall algorithm.

Example

The algorithm above is executed on the graph on the left below:

Example

In the tables below i is row numbers and j is column numbers.

Javascript Implementation

/**
 * @param {Graph} graph
 * @return {{distances: number[][], nextVertices: GraphVertex[][]}}
 */
export default function floydWarshall(graph) {
  // Get all graph vertices.
  const vertices = graph.getAllVertices()

  // Init previous vertices matrix with nulls meaning that there are no
  // previous vertices exist that will give us shortest path.
  const nextVertices = Array(vertices.length)
    .fill(null)
    .map(() => {
      return Array(vertices.length).fill(null)
    })

  // Init distances matrix with Infinities meaning there are no paths
  // between vertices exist so far.
  const distances = Array(vertices.length)
    .fill(null)
    .map(() => {
      return Array(vertices.length).fill(Infinity)
    })

  // Init distance matrix with the distance we already now (from existing edges).
  // And also init previous vertices from the edges.
  vertices.forEach((startVertex, startIndex) => {
    vertices.forEach((endVertex, endIndex) => {
      if (startVertex === endVertex) {
        // Distance to the vertex itself is 0.
        distances[startIndex][endIndex] = 0
      } else {
        // Find edge between the start and end vertices.
        const edge = graph.findEdge(startVertex, endVertex)

        if (edge) {
          // There is an edge from vertex with startIndex to vertex with endIndex.
          // Save distance and previous vertex.
          distances[startIndex][endIndex] = edge.weight
          nextVertices[startIndex][endIndex] = startVertex
        } else {
          distances[startIndex][endIndex] = Infinity
        }
      }
    })
  })

  // Now let's go to the core of the algorithm.
  // Let's all pair of vertices (from start to end ones) and try to check if there
  // is a shorter path exists between them via middle vertex. Middle vertex may also
  // be one of the graph vertices. As you may see now we're going to have three
  // loops over all graph vertices: for start, end and middle vertices.
  vertices.forEach((middleVertex, middleIndex) => {
    // Path starts from startVertex with startIndex.
    vertices.forEach((startVertex, startIndex) => {
      // Path ends to endVertex with endIndex.
      vertices.forEach((endVertex, endIndex) => {
        // Compare existing distance from startVertex to endVertex, with distance
        // from startVertex to endVertex but via middleVertex.
        // Save the shortest distance and previous vertex that allows
        // us to have this shortest distance.
        const distViaMiddle =
          distances[startIndex][middleIndex] + distances[middleIndex][endIndex]

        if (distances[startIndex][endIndex] > distViaMiddle) {
          // We've found a shortest pass via middle vertex.
          distances[startIndex][endIndex] = distViaMiddle
          nextVertices[startIndex][endIndex] = middleVertex
        }
      })
    })
  })

  // Shortest distance from x to y: distance[x][y].
  // Next vertex after x one in path from x to y: nextVertices[x][y].
  return { distances, nextVertices }
}