我正在学习计算机科学/运筹学，现在我对最大流量问题很感兴趣 . 我写了一个算法来解决这个问题，但我很难搞清楚计算的复杂性 . 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 |是顶点的数量 . 理由是：
- 在最坏的情况下，每个节点都连接到每个其他节点，因此它是一个完整的有向图 . 这意味着每个节点最多都有| 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），但我找不到其中任何一个的严格解释 . 有人能给我一个正确的方向吗？
注意：这些都不是作业，也不是任何课程的一部分 .
1 回答
复杂性
我认为由于递归调用，这对于非循环图具有指数复杂性 . （对于循环图，它永远不会完成，因此具有无限的复杂性 . ）
示例
假设我们有一个起始节点，100个节点排列在10 * 10网格中，以及一个汇聚节点 .
开始连接到第1列中的所有10个节点（容量为1） .
列x中的每个节点都连接到列x 1中的所有节点（容量为1） .
但是没有节点连接到汇聚节点 .
然后，您的算法将必须尝试通过矩阵的所有10 ^ 10（= 10,000,000,000）条可能路线，以发现最大流量等于0 .