Floyd-Warshall Algorithm Logic - Stuck

Question

I am trying to use this logic to understand what is going on with the adjacency matrix, but i am massivley confused where it says about interspacing for a b c d .....

Could anyone explain what is going on here?

Thank you (tagged as java as its the language this was demonstrated to us in, so if anyone posted any code examples they could see it was in that language)

http://compprog.wordpress.com/2007/11/15/all-sources-shortest-path-the-floyd-warshall-algorithm/

Here is the code:

for (k = 0; k < n; ++k) {
    for (i = 0; i < n; ++i)
        for (j = 0; j < n; ++j)
            /* If i and j are different nodes and if
               the paths between i and k and between
               k and j exist, do */
            if ((dist[i][k] * dist[k][j] != 0) && (i != j))
                /* See if you can't get a shorter path
                   between i and j by interspacing
                   k somewhere along the current
                   path */
                if ((dist[i][k] + dist[k][j] < dist[i][j]) ||
                        (dist[i][j] == 0))
                    dist[i][j] = dist[i][k] + dist[k][j];

Answer 1

The Floyd-Warshall algorithm does the following:

It looks at each node (k) and then looks in every k-iteration for each i, j, if it could have a shorter path by going first from i to k and then from k to j.

So it looks:

"My currently shortest path from i to j is of length L0, my currently shortest path from i to k is of length L1, my currently shortest path from k to j is of length L2.

What if I combine the currently shortest paths i to k and k to j to a new path? Is this new path i to k to j shorter than my currently shortest path i to j? If so, it accumulates the lengths L1 and L2 to compute the length of the new shortest path."

That means, k is a potential stop-over point for a way from i to j.

Answer 2

Floyd-Warshall is a dynamic programming problem.

It's almost standard (and easier) to write it in the 2-dimensional version:

for ( int k = 0; k < n; k++ )
   for ( int i = 0; i < n; i++ )
      for ( int j = 0; j < n; j++ )
          dist[i][j] = min( dist[i][k] + dist[k][j], dist[i][j] )

but perhaps it helps you to picture it with the 3-dimensional version, so you can see all the states more explicitly:

for ( int k = 0; k < n; k++ )
   for ( int i = 0; i < n; i++ )
      for ( int j = 0; j < n; j++ )
          dist[k][i][j] = min( dist[k-1][i][k] + dist[k-1][k][j], dist[i][j] )

a slightly deeper explanation of the states is found at Algorithmist.