You need to enable JavaScript to run this app. 有向网络最大流求解:同源出边流量相等约束的实现问题
优惠活动
大模型
产品
解决方案
定价
更多

有向网络最大流求解:同源出边流量相等约束的实现问题

满足源节点出边流量均等约束的最大流实现方案

核心思路

你原来的「先分配流量再回溯调整」的思路复杂度高且容易出现冲突,更稳定的实现方式是把约束内置到求解流程中,通过二分搜索+普通最大流验证的方式求解,不需要事后调整流量:

  • 假设你要求的是仅源节点的所有出边流量相等,记源节点出度为k,每条出边流量为f,那么源节点总流出流量为k*f
  • 我们只需要找到最大的可行f,即可得到满足约束的最大流

具体实现步骤

  1. 先确定f的取值范围:
    • 下限为0
    • 上限为min(源节点所有出边的容量, 无约束普通最大流总流量 / k)
  2. 对f做二分搜索:
    • 每次取中间值mid_f作为候选的单条源出边流量
    • 构造临时残留网络:将源节点的所有出边容量临时限制为mid_f,其余边容量不变
    • 在临时网络上跑普通最大流算法,得到当前最大流max_f
    • 如果max_f == k * mid_f,说明这个f是可行的,尝试搜索更大的f;否则缩小f的搜索范围
  3. 最终得到的最大可行f对应的总流量k*f就是符合约束的最大流,此时所有源出边流量均为f,自动满足约束

现有代码修改建议

你当前的find_augmenting_routes函数存在两个问题:

  • 没有判断边的残留容量,会搜索到不可行的路径
  • 没有加访问标记,遇到环会陷入无限递归

修正后的增广路径搜索+Ford-Fulkerson实现示例

class WeightedEdge:
    def __init__(self, from_vertex, to_vertex, capacity):
        self.tail = from_vertex
        self.head = to_vertex
        self.capacity = capacity
        # 新增剩余流量属性
        self.flow = 0

class Graph:
    def __init__(self, vertices, edges, capacities):
        self.vertices = vertices
        self.edges = [WeightedEdge(edges[i][0], edges[i][1], capacities[i]) for i in range(len(edges))]
        # 新增反向边存储,用于残留网络更新
        self.adj = {v: [] for v in vertices}
        for e in self.edges:
            rev_e = WeightedEdge(e.head, e.tail, 0)
            e.rev = rev_e
            rev_e.rev = e
            self.adj[e.tail].append(e)
            self.adj[e.head].append(rev_e)
    
    # 重置所有边流量,用于每次二分验证
    def reset_flow(self):
        for e in self.edges:
            e.flow = 0
            e.rev.flow = 0

# 标准Ford-Fulkerson实现
def ford_fulkerson(graph, source, sink):
    max_flow = 0
    while True:
        # DFS找增广路径
        parent = {}
        visited = set()
        def dfs(v):
            if v == sink:
                return True
            visited.add(v)
            for e in graph.adj[v]:
                if e.head not in visited and e.capacity - e.flow > 0:
                    parent[e.head] = e
                    if dfs(e.head):
                        return True
            return False
        if not dfs(source):
            break
        # 计算增广量
        min_flow = float('inf')
        v = sink
        while v != source:
            e = parent[v]
            min_flow = min(min_flow, e.capacity - e.flow)
            v = e.tail
        # 更新残留网络
        v = sink
        while v != source:
            e = parent[v]
            e.flow += min_flow
            e.rev.flow -= min_flow
            v = e.tail
        max_flow += min_flow
    return max_flow

# 最终的带约束最大流求解函数
def max_equal_split_flow(graph, source, sink):
    # 拿到源节点所有出边
    source_out_edges = [e for e in graph.edges if e.tail == source]
    k = len(source_out_edges)
    if k == 0:
        return 0
    # 求无约束最大流作为上限参考
    graph.reset_flow()
    unconstrained_max = ford_fulkerson(graph, source, sink)
    low = 0
    high = min(min(e.capacity for e in source_out_edges), unconstrained_max // k)
    best_f = 0
    # 二分搜索
    while low <= high:
        mid = (low + high) // 2
        # 临时修改源出边容量
        original_caps = [e.capacity for e in source_out_edges]
        for e in source_out_edges:
            e.capacity = mid
        graph.reset_flow()
        current_max = ford_fulkerson(graph, source, sink)
        # 恢复原容量
        for i, e in enumerate(source_out_edges):
            e.capacity = original_caps[i]
        if current_max == k * mid:
            best_f = mid
            low = mid + 1
        else:
            high = mid - 1
    # 返回总流量和每条源出边的流量
    return best_f * k, best_f

扩展场景

如果你的约束是所有节点的出边都要满足流量均等,只需要对二分逻辑做扩展:对每个中间节点,根据其入流量和出度计算每条出边的允许流量,更新对应边的容量上限后再做最大流验证即可。

内容的提问来源于stack exchange,提问作者Micheal Nestor

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.17 12:36:03