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];
}
}
My hacker page.