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