Subj : Re: Implementing A* algorithm
To   : comp.programming
From : CTips
Date : Wed Jul 20 2005 08:47 am

Huub wrote:
>>> again for more complicated graphs.
> 
> That's the point: they all have the same weight, i.e. 1. I have tried to 
> implement this into a C implementation I founnd on the net, but this 
> fails to work. This makes me think I have to use breadth-first search 
> anyway. So, I'm looking for either a C-implementation or pseudo-code I 
> can use.
>

The following (brute-force) code will give you the min distance between 
any two points. Its left as an exercise to the reader to modify it to 
actually record the min path

   unsigned Dist[15][15];
   int i, j, k, n;
   for( i = 0; i < 15; i++ ) {
     for( j = 0; j < 15; j++ ) {
       if( /* node i is connected to node j */ ) {
         Dist[i][j] = 1; /* min path is <i,j> */
       }
       else {
         Dist[i][j] = 15; /* min path is empty */
      }
     }
   }

   for( n = 0; n < 15; n++ ) {
     for( i = 0; i < 15; i++ ) {
       for( j = 0; j < 15; j++ ) {
         d = 15;
         for( k = 0; k < 15; k++ ) {
           if( Dist[i][k] + Dist[k][j] < d ) {
             d = Dist[i][k] + Dist[k][j];
            /* min path is min-path(i->k) concat with min-path(k->j) */
           }
         }
         Dist[i][j] = d;
         /* record new min-path */
        }
      }
    }

.