在加权定向循环图中寻找从A到B的不同路径的算法

Question

假设我们有一个DIRECTED,WEIGHTED和CYCLIC图表.

假设我们只对总重量小于MAX_WEIGHT的路径感兴趣

找到总重量小于MAX_WEIGHT的两个节点A和B之间的不同路径数量的最合适(或任何)算法是什么？

PS:这不是我的功课.只是个人的非商业项目.

Answer 1

如果节点 和 的数量MAX_WEIGHT不是太大（并且所有权重都是整数），则可以使用动态规划

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

初始化为 0，除了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];
             */
        }
    }
}

解是 的总和num_of_paths[w][target], 0 <= w <= MAX_WEIGHT。