information:highlighting, information:extraction
Algorithm

The Floyd–Warshall algorithm compares many possible paths through the graph between each pair of vertices. It is guaranteed to find all shortest paths and is able to do this with Θ (| V | 3) {\displaystyle \Theta (|V|^{3})} comparisons in a graph, even though there may be Θ (| V | 2) {\displaystyle \Theta (|V|^{2})} edges in the graph. It does so by incrementally improving an estimate on the shortest path between two vertices, until the estimate is optimal.

Consider a graph G {\displaystyle G} with vertices V {\displaystyle V} numbered 1 through N {\displaystyle N}. Further consider a function s h o r t e s t P a t h (i, j, k) {\displaystyle \mathrm {shortestPath} (i,j,k)} that returns the length of the shortest possible path (if one exists) from i {\displaystyle i} to j {\displaystyle j} using vertices only from the set { 1, 2, …, k } {\displaystyle \{1,2,\ldots,k\}} as intermediate points along the way. Now, given this function, our goal is to find the length of the shortest path from each i {\displaystyle i} to each j {\displaystyle j} using any vertex in { 1, 2, …, N } {\displaystyle \{1,2,\ldots,N\}}. By definition, this is the value s h o r t e s t P a t h (i, j, N) {\displaystyle \mathrm {shortestPath} (i,j,N)}, which we will find recursively.

Observe that s h o r t e s t P a t h (i, j, k) {\displaystyle \mathrm {shortestPath} (i,j,k)} must be less than or equal to s h o r t e s t P a t h (i, j, k − 1) {\displaystyle \mathrm {shortestPath} (i,j,k-1)}: we have more flexibility if we are allowed to use the vertex k {\displaystyle k}. If s h o r t e s t P a t h (i, j, k) {\displaystyle \mathrm {shortestPath} (i,j,k)} is in fact less than s h o r t e s t P a t h (i, j, k − 1) {\displaystyle \mathrm {shortestPath} (i,j,k-1)}, then there must be a path from i {\displaystyle i} to j {\displaystyle j} using the vertices { 1, 2, …, k } {\displaystyle \{1,2,\ldots,k\}} that is shorter than any such path that does not use the vertex k {\displaystyle k}. Since there are no negative cycles this path can be decomposed as:

And of course, these must be a shortest such path (or several of them), otherwise we could further decrease the length. In other words, we have arrived at the recursive formula:

The base case is given by

where w (i, j) {\displaystyle w(i,j)} denotes the weight of the edge from i {\displaystyle i} to j {\displaystyle j} if one exists and ∞ (infinity) otherwise.

These formulas are the heart of the Floyd–Warshall algorithm. The algorithm works by first computing s h o r t e s t P a t h (i, j, k) {\displaystyle \mathrm {shortestPath} (i,j,k)} for all (i, j) {\displaystyle (i,j)} pairs for k = 0 {\displaystyle k=0}, then k = 1 {\displaystyle k=1}, then k = 2 {\displaystyle k=2}, and so on. This process continues until k = N {\displaystyle k=N}, and we have found the shortest path for all (i, j) {\displaystyle (i,j)} pairs using any intermediate vertices. Pseudocode for this basic version follows.