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.

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}`

.

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

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

In the tables below `i`

is row numbers and `j`

is column numbers.

```
/**
* @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 }
}
```