最小费用流问题中无限供应节点的处理方案咨询

问题分析 #

核心矛盾是NetworkX的min_cost_flow系列函数要求图的总节点需求和为0，但标记为NA的无限供应节点无法用常规demand值处理：设0会打破总需求平衡，设大整数也无法匹配动态的总需求。无限供应节点的本质是可提供任意多流量，无需考虑自身供应上限，需通过超级源点来统一建模。

解决思路 #

1. 计算总需求：统计所有demand为数值的节点需求之和，得到网络需要的总供应量。
2. 添加超级源点：设置该节点的demand为负的总需求量，表示它要提供对应流量。
3. 转换无限供应节点：将NA节点的demand设为0（作为中转节点），从超级源点向每个这类节点添加一条容量无限大、权重为0的边，模拟无限供应特性。
4. 修正边参数：确保所有原始边都正确设置capacity参数（你之前的代码遗漏了这个关键项）。

修改后的代码 #

def solve(N,E):
    G = nx.DiGraph()
    
    # 计算所有非无限供应节点的总需求
    total_demand = 0
    for node_attr in N.values():
        if node_attr["demand"] != 'NA':
            total_demand += int(node_attr["demand"])
    
    # 添加超级源点，承担总供应任务
    super_source = 0
    G.add_node(super_source, demand=-total_demand)
    
    # 逐个添加节点并处理无限供应情况
    for node_id, node_attr in N.items():
        if node_attr["demand"] == 'NA':
            # 无限供应节点设为中转节点，demand为0
            demand = 0
            # 超级源点到该节点的边：无限容量、0成本
            G.add_edge(super_source, node_id, capacity=float('inf'), weight=0)
        else:
            demand = int(node_attr["demand"])
        G.add_node(node_id, demand=demand)

    # 添加原始边，同时设置容量和权重
    for (start, end), capacity in E.items():
        start_pos = N[start]['pos']
        end_pos = N[end]['pos']
        G.add_edge(start, end, capacity=capacity, weight=cost_edge(start_pos, end_pos))
 
    return nx.min_cost_flow_cost(G)

关键说明 #

• 超级源点的作用是统一提供网络所需总流量，确保全图总需求和为0，满足NetworkX的约束。
• 无限供应节点通过超级源点获取流量后转发给下游需求节点，完美模拟“无限供应”的特性。
• 原始边必须明确设置capacity，否则NetworkX会默认边容量无限，违背给定的边限制规则。

内容的提问来源于stack exchange，提问作者maxJump10th