NetworkX中满足路由约束的全量最短路径求解方案咨询

现有生成器的后续处理方法 #

你首先需要提前定义好所有源目节点对的约束规则，示例如下：

# 约束配置字典，key为源目节点元组，value为(必经节点集合, 禁行节点集合)
path_constraints = {
    ('A', 'E'): ({'B', 'C'}, {'D'}),
    ('B', 'D'): ({'A'}, {'C'}),
    # 补充所有endPoints两两组合的约束
}

之后遍历生成器筛选符合规则的路径，再取最短加权路径即可：

import networkx as nx

def get_pair_constraint(s, d):
    # 适配无向图源目顺序互换的场景
    return path_constraints.get((s,d)) or path_constraints.get((d,s))

valid_result = []
weight_field = "weight" # 替换为你图里的边权字段名

for s, d, path_generator in allPaths:
    required_nodes, forbidden_nodes = get_pair_constraint(s, d)
    qualified_paths = []
    # 遍历生成器产出的所有简单路径
    for path in path_generator:
        path_node_set = set(path)
        # 排除包含禁行节点的路径
        if path_node_set & forbidden_nodes:
            continue
        # 排除未覆盖所有必经节点的路径
        if not required_nodes.issubset(path_node_set):
            continue
        # 计算当前路径的加权总长度
        total_length = nx.path_weight(G, path, weight=weight_field)
        qualified_paths.append((total_length, path))
    if qualified_paths:
        # 取加权长度最小的路径作为当前s-d对的结果
        min_len, min_path = min(qualified_paths)
        valid_result.append((s, d, min_len, min_path))

注意：该方案仅适合节点规模极小的场景，90节点的图简单路径数量为指数级，实际运行会出现耗时极长、内存溢出的问题，不推荐在你的场景下使用。

性能更优的替代方案 #

推荐使用子图裁剪+必经节点排列的方案，时间复杂度可控，适配你的节点规模：

• 对每对s,d节点，先从原图中删除所有该对对应的禁行节点，生成子图G_sub
• 提取当前s,d对对应的必经节点列表R：
  • 如果R为空，直接调用nx.shortest_path(G_sub, s, d, weight=weight_field)得到最短路径即可
  • 如果R不为空，生成R的所有全排列，对每个排列[r1, r2, ..., rk]，按顺序计算s→r1、r1→r2、...、rk→d的最短路径长度之和，取总长度最小的排列对应的拼接路径即为符合要求的最短路径
• 若必经节点数量超过8，可改用动态规划优化排列计算环节，进一步降低耗时。

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