Editing Floyd–Warshall algorithm (section)

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

[[File:Floyd-Warshall example.svg|600px]]

Prior to the first recursion of the outer loop, labeled {{math|1=''k'' = 0}} above, the only known paths correspond to the single edges in the graph. At {{math|1=''k'' = 1}}, paths that go through the vertex 1 are found: in particular, the path [2,1,3] is found, replacing the path [2,3] which has fewer edges but is longer (in terms of weight). At {{math|1=''k'' = 2}}, paths going through the vertices {1,2} are found. The red and blue boxes show how the path [4,2,1,3] is assembled from the two known paths [4,2] and [2,1,3] encountered in previous iterations, with 2 in the intersection. The path [4,2,3] is not considered, because [2,1,3] is the shortest path encountered so far from 2 to 3. At {{math|1=''k'' = 3}}, paths going through the vertices {1,2,3} are found. Finally, at {{math|1=''k'' = 4}}, all shortest paths are found.

The distance matrix at each iteration of {{mvar|k}}, with the updated distances in '''bold''', will be:
{| class=wikitable style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" |{{math|1=''k'' = 0}}
| colspan="4" |{{mvar|j}}
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |{{mvar|i}}
! 1
| 0 || &infin; || −2 || &infin;
|-
! 2
| 4 || 0 || 3 || &infin;
|-
! 3
| &infin; || &infin; || 0 || 2
|-
! 4
| &infin; || −1 || &infin; || 0
|}

{| class=wikitable style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" |{{math|1=''k'' = 1}}
| colspan="4" |{{mvar|j}}
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |{{mvar|i}}
! 1
| 0 || &infin; || −2 || &infin;
|-
! 2
| 4 || 0 || '''2''' || &infin;
|-
! 3
| &infin; || &infin; || 0 || 2
|-
! 4
| &infin; || −1 || &infin; || 0
|}

{| class=wikitable style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" |{{math|1=''k'' = 2}}
| colspan="4" |{{mvar|j}}
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |{{mvar|i}}
! 1
| 0 || &infin; || −2 || &infin;
|-
! 2
| 4 || 0 || 2 || &infin;
|-
! 3
| &infin; || &infin; || 0 || 2
|-
! 4
| '''3''' || −1 || '''1''' || 0
|}

{| class=wikitable style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" |{{math|1=''k'' = 3}}
| colspan="4" |{{mvar|j}}
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |{{mvar|i}}
! 1
| 0 || &infin; || −2 || '''0'''
|-
! 2
| 4 || 0 || 2 ||'''4'''
|-
! 3
| &infin; || &infin; || 0 || 2
|-
! 4
| 3 || −1 || 1 || 0
|}

{| class=wikitable style="float:left; margin:10px; text-align:center;"
|+
| colspan="2" rowspan="2" |{{math|1=''k'' = 4}}
| colspan="4" |{{mvar|j}}
|-
! 1 !! 2 !! 3 !! 4
|-
| rowspan="4" |{{mvar|i}}
! 1
| 0 || '''−1''' || −2 || 0
|-
! 2
| 4 || 0 || 2 || 4
|-
! 3
| '''5''' || '''1''' || 0 || 2
|-
! 4
| 3 || −1 || 1 || 0
|}
{{clear}}