Warshall Algorithm Logic - Stuck
- by stan
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];