File:Floyd-Warshall example.svg

English: Demonstration of Floyd-Warshall algorithm for all-pairs shortest path on a directed graph with 4 vertices. At k=0, prior to the first iteration of the outer loop, the only known paths correspond to single edges in the original graph. At 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 less edges but is longer. At 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 known paths 4→2 and 2→1→3 encountered in previous iterations. The path 4→2→3 is not considered, because it is already known that 2→1→3 is the shortest path from 2 to 3. At k=3, paths going through the vertices {1,2,3} are found. Finally, at k=4, all shortest paths are found.