Algorithm for finding distinct paths from A to B in weighted, directed, cyclic graph

Question

Suppose we have a DIRECTED, WEIGHTED and CYCLIC graph.

Suppose we are only interested in paths with a total weight of less than MAX_WEIGHT

What is the most appropriate (or any) algorithm to find the number of distinct paths between two nodes A and B that have a total weight of less than MAX_WEIGHT?

P.S: It's not my homework. Just personal, non-commercial project.

Answer 1

If the number of nodes and MAX_WEIGHT aren't too large (and all weights are integers), you can use dynamic programming

unsigned long long int num_of_paths[MAX_WEIGHT+1][num_nodes];

initialize to 0, except num_of_paths[0][start] = 1;.

for(w = 0; w < MAX_WEIGHT; ++w){
    for(n = 0; n < num_nodes; ++n){
        if (num_of_paths[w][n] > 0){
            /* for each child c of node n
             * if w + weight(n->c) <= MAX_WEIGHT
             * num_of_paths[w+weight(n->c)][c] += num_of_paths[w][n];
             */
        }
    }
}

solution is sum of num_of_paths[w][target], 0 <= w <= MAX_WEIGHT .