Subj : Re: Implementing A* algorithm
To   : comp.programming
From : Huub
Date : Wed Jul 20 2005 03:10 pm

CTips wrote:
> 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 */
>        }
>      }
>    }

Thank you.

.