Warshall Algorithm Logic - Stuck

Posted by stan on Stack Overflow See other posts from Stack Overflow or by stan
Published on 2010-04-22T08:45:58Z Indexed on 2010/04/22 9:13 UTC
Read the original article Hit count: 306

Filed under:
|
|

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

© Stack Overflow or respective owner

Related posts about algorithm

Related posts about revision