如何在带边容量的无向图中查找满足需求的简单路径？

问题描述 #

给定带边容量属性的无向图G，输入源节点（SourceNode）、目标节点（TargetNode）和需求值（demand），需要找出所有简单路径（路径中无重复节点），要求路径上的每条边的capacity属性值都≥demand。

已知NetworkX的network_simplex()或min_cost_flow()仅能返回流形式结果，无法直接得到所需的路径列表，因此需要另一种实现方式。

解决方案思路 #

核心逻辑是先过滤出符合容量要求的子图，再在子图中查找所有源到目标的简单路径：

• 第一步：从原图中筛选出所有capacity ≥ demand的边，构建一个只包含这些边的子图。这样子图中的任意路径天然满足容量约束。
• 第二步：在这个子图中，使用NetworkX的路径查找工具获取所有源到目标的简单路径。
• 第三步：将路径格式化为指定的字符串形式（如"a,c,d"）。

代码实现 #

import networkx as nx

def find_valid_paths(G, source, target, demand):
    # 构建符合容量要求的子图
    valid_edges = [(u, v) for u, v, attrs in G.edges(data=True) if attrs.get('capacity', 0) >= demand]
    subgraph = nx.Graph()
    subgraph.add_edges_from(valid_edges)
    
    # 检查源和目标是否在子图中连通，不连通直接返回空列表
    if not nx.has_path(subgraph, source, target):
        return []
    
    # 获取所有简单路径并格式化
    all_paths = nx.all_simple_paths(subgraph, source=source, target=target)
    formatted_paths = [','.join(path) for path in all_paths]
    return formatted_paths

# 示例测试
if __name__ == "__main__":
    G = nx.Graph()
    G.add_edge("a", "b", capacity=4)
    G.add_edge("a", "c", capacity=10)
    G.add_edge("b", "d", capacity=9)
    G.add_edge("c", "d", capacity=5)
    
    # 调用函数，需求值为5
    result = find_valid_paths(G, "a", "d", demand=5)
    print(result)  # 输出: ['a,c,d']

说明 #

• 若原图中不存在满足容量要求的连通路径（比如源和目标在筛选后的子图中不连通），函数返回空列表。
• nx.all_simple_paths()会枚举所有不重复经过节点的路径，完全符合问题中"简单路径"的要求。
• 代码中默认边的capacity属性存在，若部分边无该属性，会默认按0处理（即不满足任何正需求）。

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