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

Question

假设我们有一个有向的（DIRECTED），加权的（WEIGHTED）和循环的（CYCLIC）图。

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

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

附注：这不是我的作业。只是个人、非商业项目。

- Babak

---

您是否允许路径多次经过同一顶点（路径长度小于MAX_WEIGHT）？ - NPE

我们可以假设没有零权重的循环吗？ - user684934

@aix：是的，抱歉忘了提。只要满足MAX_WEIGHT的条件，您可以循环任意次数。 - Babak

@bdares：我不太确定零权重循环是什么意思。你可以假设每条边的权重都大于0。 - Babak

“distinct paths”的意思是什么？ - Saeed Amiri

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。

- Daniel Fischer

---

如果你能用这种方法解决，那么你可以在O(n*MAX_WEIGHT)的时间复杂度内解决k-不相交路径的一般情况。如果您假设所有边缘的权重是“1”，则可以在O(n^3)内解决它，但在这种情况下，它是NP难问题。 - Saeed Amiri

错误，distinct != disjoint。A -> B -> C -> D 和 A -> C -> B -> D 是从 A 到 D 的两条不同路径。 - Daniel Fischer

你所说的是k边不相交路径问题。而且我不认为OP这么说过。另外，在边不相交路径中，你也不能这样做。 - Saeed Amiri

@Saeed 我觉得你基本上是误解了。当然可能是我，但我觉得是你。我的算法中没有任何不连续性，并且问题陈述中也没有提到任何不连续性。比之前更好的例子可能是 A -> B -> D -> E 和 A -> C -> D -> E。这两条路径是从 A 到 E 的两条不同路径，但它们有共同的顶点和边。 - Daniel Fischer

让我们在聊天中继续这个讨论。点击此处进入聊天室。 - Saeed Amiri

Answer 2

简单递归。您需要指数时间来完成。显然，不允许有零权重循环。

函数noe（节点N，限制权重W）

1. 如果所有出边的权重都大于W，则路径数为零

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

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

- Boris Stitnicky

Answer 3

你的问题是有向平面图中K条不相交路径的一般情况, 其中K没有固定。

对于有向平面图的K个不相交路径问题如下：

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

找到：在 G 中，k 条两两不相交的有向路径 P₁；...；P_k，其中 P_i 从 r_i 到 s_i（i=1;....;k）。

在 K-Disjoint Path 中，您可以从所有 s_i 到 B 绘制弧线，也可以从 A 到所有 r_i 绘制弧线，通过这种方式，您可以从 G 创建图 G'。

现在，如果您可以在 G' 中解决问题，则可以在 G 中解决 k-disjoint Path，因此 P=NP。

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

此外，还有更复杂的算法可以在一般图中解决这个问题（对于固定的k），但总体来说并不容易（由Seymour提出）。

因此，目前你最好的选择是使用暴力算法。

编辑：由于MAXWEIGHT与您的输入大小（您的图形大小）无关，因此它不会影响此问题。另外，由于对于无向无权图而言，它是NP-Hard的，因此您仍然可以简单地得出它是NP-Hard的结论。

- Saeed Amiri

---

如果您对此主题感兴趣，可以查看http://homepages.cwi.nl/~lex/files/agt3.pdf以获取更多相关内容。 - Saeed Amiri