Floyd's algorithm
In article <adams-2304960109500001@rerun.jj.rhno.columbia.edu>
in comp.lang.c,
Adam Saper writes:
Does anyone know if it is possible for floyd's algorithm can be modified
to return the actual shortest path and not just the length. This
algorithm, now, finds the shortest distance between two nodes on a graph
represented by a matrix of distances.
This is my guess:
void floyd()
{
int u, v, w;
int changed = 1;
for (v = 0; v < MAX; v++)
for (w = 0; w < MAX; w++)
{ shortest[v][w] = dist[v][w];
to[v][w] = w;
}
while (changed)
{ changed = 0;
for (u = 0; u < MAX; u++)
for (v = 0; v < MAX; v++)
for (w = 0; w < MAX; w++)
if (shortest[v][u] + shortest[u][w] < shortest[v][w])
{ shortest[v][w] = shortest[v][u] + shortest[u][w];
to[v][w] = to[v][u];
changed = 1;
}
}
}
void print_shortest(int a, int b)
{
printf("the shortest path between %d and %b consists of:\n", a, b);
while (a != b)
{ printf("from %d goto %d (distance %d)\n", a, to[a][b], shortest[a][b]);
a = to[a][b];
}
}
I discovered this algorithm all by myself on
December 28, 1980
(Dutch).
Actually, the above is wrong!!
On April 11, 2005, I discovered that the above is actually not Floyd's algorithm.
When making some search for an algorithm for calculating the transitive closure,
I came across the mentioning of Warshall's algorithm, on which Floyd's algorithm
is based. I discovered that the outer-loop ("while (changed)") is not
needed at all. It sounds rather surprising, but it is true for the given nesting
order of the loops, where the outer-loop runs over the middle element (u
in this case). For all nesting orders where the middle element is not in the outer-loop
it does not work. For a proof of this see these slides.
My hacker page