[algogeeks] Re: find all paths from one node to another node

[Omar Haider]

hi everyone ,
what i propose for this very problem , if i understand it correctly , is to use recursion with memoization ...
let us assume that we want to know the number of paths in a directed graph between 2 of its vertices u and v ...
what we do is write this simple memoization :

# define number_of_nodes 100

typedef long long myint ;
int u , v ;
myint cache[number_of_node + 10 ];
myint go( int  x ){
     myint& ret  = cache[x]  ;
     if( ret !=-1 ) return ret ;
     if( x == v ) return ret == 1 ;
    
     ret = 0 ;
    
     for( i = 0 ; i < out_deg[ x ] ; ++i ){
            ret += go( neighbour[ x ].adj[ i ] ) ;
     }

     return ret ;
 
}

int main( ){
    for( i = 0 ; i < no_of_nodes ;++i ) cache[ i] = 0xffffffff ;
    myint ret = go( u ) ;
    print ------> ret ;  
    return 0 ;
}

Warning : the code above is not tested , it is spontaneously written in the mail editor  , so any error  in the idea can happen  ............
bye bye
tc
Riyad

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---