Editing Floyd–Warshall algorithm (section)

==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 <math>\Theta(|V|^3)</math> comparisons in a graph,<ref name=":0" /><ref name=":1" /> even though there may be <math>\Theta (|V|^2)</math> 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 <math>G</math> with vertices <math>V</math> numbered 1 through&nbsp;<math>N</math>. Further consider a function <math>\mathrm{shortestPath}(i,j,k)</math> that returns the length of the shortest possible path (if one exists) from <math>i</math> to <math>j</math> using vertices only from the set <math>\{1,2,\ldots,k\}</math> as intermediate points along the way.  Now, given this function, our goal is to find the length of the shortest path from each <math>i</math> to each <math>j</math> using ''any'' vertex in <math>\{1,2,\ldots,N\}</math>. By definition, this is the value <math>\mathrm{shortestPath}(i,j,N)</math>, which we will find [[Recursion|recursively]].

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

:(1) a path from <math>i</math> to <math>k</math> that uses the vertices <math>\{1,2,\ldots,k-1\}</math>, followed by

:(2) a path from <math>k</math> to <math>j</math> that uses the vertices <math>\{1,2,\ldots,k-1\}</math>.

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:
: <math>\mathrm{shortestPath}(i,j,k) =</math>
:: <math>\mathrm{min}\Big(\mathrm{shortestPath}(i,j,k-1),</math>
::: <math>\mathrm{shortestPath}(i,k,k-1)+\mathrm{shortestPath}(k,j,k-1)\Big)</math>.
The base case is given by
: <math>\mathrm{shortestPath}(i,j,0) = w(i,j),</math>
where <math>w(i,j)</math> denotes the weight of the edge from <math>i</math> to <math>j</math> if one exists and ∞ (infinity) otherwise.

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

===Pseudocode===

 '''let''' dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
 '''for each''' edge (''u'', ''v'') '''do'''
     dist[''u''][''v''] = w(''u'', ''v'')  ''// The weight of the edge (''u'', ''v'')''
 '''for each''' vertex ''v'' '''do'''
     dist[''v''][''v''] = 0
 '''for''' ''k'' '''from''' 1 '''to''' |V|
     '''for''' ''i'' '''from''' 1 '''to''' |V|
         '''for''' ''j'' '''from''' 1 '''to''' |V|
             '''if''' dist[''i''][''j''] > dist[''i''][''k''] + dist[''k''][''j''] 
                 dist[''i''][''j''] = dist[''i''][''k''] + dist[''k''][''j'']
             '''end if'''