Floyd–Warshall Algorithm
Algorithm · Stretch
Step through it: Weighted Shortest Path pattern
Step 1 of 6
Goal: the cheapest route from A to every place when roads have different costs: A→B 4, A→C 1, C→B 2, B→D 1. Keep a table of the best known cost to each place: 0 for A, unknown for the rest.
Step 2 of 6
Always finish the closest unfinished place first: A (cost 0). Try its roads: B costs 0 + 4 = 4 and C costs 0 + 1 = 1.
Step 3 of 6
The closest unfinished place is now C (1). The road C→B gives B a cost of 1 + 2 = 3, cheaper than 4, so update B.
Step 4 of 6
Closest unfinished: B (3). The road B→D gives D a cost of 3 + 1 = 4.
Step 5 of 6
The cheapest A to D is 4, via A, C, B, D. Finishing the closest place first guarantees no later road can beat it, as long as no cost is negative. A priority queue finds the closest place quickly. This is Dijkstra's algorithm.
Step 6 of 6
Your turn.
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}.
This formula is the heart of the Floyd–Warshall algorithm.
Example
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.
k = 0
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | ∞ | −2 | ∞ |
| 2 | 4 | 0 | 3 | ∞ |
| 3 | ∞ | ∞ | 0 | 2 |
| 4 | ∞ | −1 | ∞ | 0 |
k = 1
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | ∞ | −2 | ∞ |
| 2 | 4 | 0 | 2 | ∞ |
| 3 | ∞ | ∞ | 0 | 2 |
| 4 | ∞ | − | ∞ | 0 |
k = 2
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | ∞ | −2 | ∞ |
| 2 | 4 | 0 | 2 | ∞ |
| 3 | ∞ | ∞ | 0 | 2 |
| 4 | 3 | −1 | 1 | 0 |
k = 3
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | ∞ | −2 | 0 |
| 2 | 4 | 0 | 2 | 4 |
| 3 | ∞ | ∞ | 0 | 2 |
| 4 | 3 | −1 | 1 | 0 |
k = 4
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | −1 | −2 | 0 |
| 2 | 4 | 0 | 2 | 4 |
| 3 | 5 | 1 | 0 | 2 |
| 4 | 3 | −1 | 1 | 0 |
Code
/**
* @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 };
}References
Practice
Weighted Shortest Path
- Network Delay TimeMedium
- Cheapest Flights Within K StopsMedium
- Path With Minimum EffortMedium
- Path with Maximum ProbabilityMedium
- Find the City With the Smallest Number of NeighborsMedium
- Minimum Cost to Reach Destination in TimeMedium
- Swim in Rising WaterHard
- Minimum Cost to Make at Least One Valid Path in a GridHard
Spotted a mistake or something unclear? Report it on GitHub.