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];

@stan: Floyd-Warshall is one of the typical "DP algo", along with Levenhstein's Edit Distance and the "0-1 Knapsack". To understand it you need to understand what "Dynamic Programming" is about (most programmers that haven't a CS degree don't know anything about DP). The Wikipedia entry on the subject is good: http://en.wikipedia.org/wiki/Dynamic_programming and otherwise you can try to participate in a few online competition (like TopCoder), where typically quite a lot of the problems need a DP solution. — SyntaxT3rr0r, Apr 22 '10 at 10:50

Larry · Answer 1 · 2014-08-15T05:59:43.627

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.

In you last line of code there should be dist[k-1][i][j] instead of dist[i][j] I think — Karussell, Jan 22 '12 at 22:19

score 4 · Answer 2 · edited Apr 22 '10 at 10:45

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.

Floyd-Warshall Algorithm Logic - Stuck

2 Answers2