2

我正在学习计算机科学/运筹学，现在我对最大流量问题感兴趣。我写了一个算法来解决这个问题，但在计算复杂度方面遇到了麻烦。Python-esque 伪代码如下：

function max_flow(graph,current_node,limit):
    if limit <= 0:
        return 0 
    else if node == graph.sink:
        return limit
    else:
        total = 0
        for each node connected to current_node:
            cap = graph.capacity(current_node,node)
            if cap > 0:
                next_limit = min(cap, limit - total)
                next_max_flow = max_flow(graph,node,next_limit)
                total += next_max_flow
                graph.capacity(current_node,node) -= next_max_flow
        return total

其中 graph.capacity(a,b) 表示从 a 到 b 的弧的容量。要找到总最大流量，可以将该算法称为 max_flow(graph,graph.source,infinity)。

我向自己证明了该算法是正确的（尽管如果这也是错误的，请随时纠正我），并且我对复杂性的信念是该算法在 O(|V| 2 ) 中运行，其中 |V| 是顶点的数量。理由是：

  1. 在最坏的情况下，每个节点都连接到其他每个节点，因此它是一个完整的有向图。这意味着每个节点最多有 |V| - 1 条边。但是，由于倾斜对称性，如果从 a 到 b 的容量为正，则从 b 到 a 的容量必须为负。所以，如果源有 |V| - 1 个正容量边，那么次高节点最多可以有 |V| - 2 个正容量边，因为至少一个边必须具有负容量。因此，正容量边的总数最多为 (|V|-1)*(|V|-2) / 2 = O(|V| 2 )。

这就是我卡住的地方。直觉上，这听起来像是经历了每一个 |V| 节点最大 |V| 次，结果为 O(|V| 2 )。然而，我的一部分认为实际的复杂性是 O(|V| 3 )，但我找不到任何严格的解释。有人可以推动我朝着正确的方向前进吗？

注意：这些都不是家庭作业，也不是任何课程的一部分。

4

1 回答 1

0

复杂

我认为由于递归调用，这对于非循环图具有指数复杂性。（对于循环图，它永远不会完成，因此具有无限的复杂性。）

例子

假设我们有一个起始节点，100 个节点排列在一个 10*10 的网格中，还有一个汇节点。

start 连接到第 1 列中的所有 10 个节点（容量为 1）。

x 列中的每个节点都连接到 x+1 列中的所有节点（容量为 1）。

但是没有节点连接到汇节点。

然后您的算法将不得不尝试通过矩阵的所有 10^10 (= 10,000,000,000) 条可能的路线，以发现最大流量等于 0。

于 2017-05-10T18:26:25.267 回答