How is Floyd-Warshall a Dynamic Algorithm?

Question

Since the Floyd-Warshall algorithm is dynamic, that means that it must provide an optimum solution at all times, right? So what's confusing me is what the nature of these optimum solutions is during each segment of the algorithm - in particular, I'm trying to understand the following three questions:

• iteration 0: what optimum (i.e. exact) solution is provided before any iteration occurs?

• iteration 1: what optimum (i.e. exact) solution is provided at the end of this iteration?

• iteration i (for arbitrary i > 0): what optimum (i.e. exact) solution is provided at the end of this iteration?

Can anyone shed some light on these concerns?

Answer 1

Recall that the outer loop iterates k, the "intermediate" vertex though which the candidate path from i to j could go:

for k in 0..N-1
    for i in 0..N-1
        for j in 0..N-1
            g[i,j] = min(g[i,j], g[i,k]+g[k,j])

Therefore, before all the iterations the partial solution (which at this point is equivalent to the unmodified adjacency matrix) represents a subset of the final solution where all shortest paths that go directly from i to j are represented.

After one iteration, the shortest paths that go through the first vertex (at index 0) are added to the mix.

After K iterations, the partial solution contains shortest paths that are either (1) direct, or (2) go through one or more vertexes from the set of {0..K-1}, inclusive. Of course once K reaches N, the solution is complete.

Answer 2

Iteration 0 : Before any iteration the optimum solution obtained contains the nodes that can be reached without traversing any nodes. So before the first iteration you know only know the distance of a node from itself, and the distance from a node to itself is 0.

Iteration 1 : After the first iteration you will have the distance between any two nodes directly connected by an edge.

Iteration i : After iteration i you will have the distance between any two nodes separated by not more than i edges.