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

Question

假设我们有一个有向、加权和循环图。

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

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

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 的总和。

Answer 2

简单的递归。你在指数时间内就拥有了它。显然，不允许零重量循环。

函数 noe(节点 N, 限制权重 W)

1. no.如果所有传出边的权重均大于 1，则路径的 0 为零。没有

2. 否则不行。路径的数量是通过 sum(noe(C1,W-W1),noe(C2,W-W2),... noe(Cn,W-Wn)) 获得的路径数的总和，其中 C1 ... Cn 是连接到 N 的节点，其中 W-Wi 不为负，其中 Wi 是连接边的权重，用您最喜欢的语言编写。

按照 Dijkstra 算法的思路，应该存在更有效的解决方案，但我认为这对于家庭作业来说已经足够了。

Answer 3

您的问题是K-不相交路径在有向平面图中的更一般情况，有向平面图的

K 不相交路径问题如下：

给定：有向平面图 G = (V;E) 和 k 对(r₁; s₁); ....; G 顶点的 (r_k; s_k)；

查找：k个成对顶点不相交的有向路径P₁； ...; G 中的 P_k，其中 P_i 从 r_i 到 s_i (i = 1; .. ..；k）。

在k-不相交路径中，您可以绘制从所有 s_i 到 B 的弧，也可以从 A 到所有 r_i 的弧，通过这种方式您可以从 G 创建图 G'。

现在，如果您可以解决 P 中 G' 中的问题，您就可以解决 G 中的 k 不相交路径，因此 P=NP。

但是，如果您阅读链接的论文，它会给出一些关于一般图的想法（用固定 k 求解 k 不相交路径），您可以使用它来获得一些好的近似值。

还有更复杂的算法可以在一般图中解决 P（对于固定 k）中的这个问题。但总而言之，这并不容易（作者：Seymour）。

所以目前你最好的选择是使用暴力算法。

编辑：因为 MAXWEIGHT 与你的输入大小（你的图形大小）无关，所以它不会影响这个问题，而且因为它对于无向无权图来说是 NP-Hard，所以你仍然可以简单地得出结论它是 NP-难的。