Floyd-Warsall Logic Logic - Stuck

Question

I am trying to use this logic to understand what is happening with the adjacency matrix , but I am very confused when it talks about interpacing for abcd .....

Can someone explain what is going on here?

Thanks. (marked as java as the language in which it was demonstrated to us, so if someone had published code examples, they could see that 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 is almost standard (and easier) to write it in a two-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 this will help you present it with a 3-dimensional version so that you can see all the states more clearly:

 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 somewhat deeper explanation of states is found on the Algorithmist .

Answer 2

The Floyd-Warsall algorithm performs the following actions:

He looks at each node ( k ) and then looks at each k iteration for each i, j , if he can have a shorter path, going from i to k and then from k to j .

So it looks like:

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

What if I match the current shortest paths i to k and k to j with the new path? Is this new path i to k to j shorter than my shortest path i to j ? If so, it accumulates the lengths L1 and L2 to calculate the length of the new shortest path. "

This means that k is a potential stopping point for the path from i to j .