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

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[k-1][i][j] )

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