NetworkX无需添加边权重属性计算两节点间所有最短路径的方法

NetworkX 官方提供的 all_shortest_paths 接口目前不支持直接传入自定义权重函数，仅支持读取边属性作为权重值，但可以通过以下两种方案实现需求，无需永久修改原图的边属性：

方案1：先求最短长度再筛选路径 #

适合中小规模、s到t的简单路径数量不多的场景：

# 第一步：调用已有的single_source_dijkstra拿到s到t的最短路径长度
min_dist, _ = nx.single_source_dijkstra(G, source=s, target=t, weight=f)

result = []
# 遍历所有s到t的简单路径
for path in nx.all_simple_paths(G, source=s, target=t):
    # 用自定义权重函数计算当前路径总权重
    total_weight = 0
    for u, v in zip(path[:-1], path[1:]):
        total_weight += f(u, v, G.edges.get((u, v), {}))
    # 筛选出总权重等于最短长度的路径
    if total_weight == min_dist:
        result.append((total_weight, path))

该方案完全不修改原图结构，适配任意自定义权重函数，仅在路径数量过多时性能较差。

方案2：生成带临时权重属性的副本 #

适合大规模图、对性能要求较高的场景：

# 生成原图副本，避免修改原图
G_temp = G.copy()
# 用自定义权重函数预计算所有边的权重，写入临时边属性
for u, v, attr in G_temp.edges(data=True):
    attr['temp_weight'] = f(u, v, attr)

# 直接调用原生all_shortest_paths接口
min_dist, _ = nx.single_source_dijkstra(G, source=s, target=t, weight=f)
all_shortest = nx.all_shortest_paths(G_temp, source=s, target=t, weight='temp_weight', method='dijkstra')
# 组装为要求的(路径长度, 路径)格式
result = [(min_dist, path) for path in all_shortest]

# 用完可直接删除临时图，不影响原有数据
del G_temp

该方案复用了NetworkX原生优化的最短路径计算逻辑，性能远高于第一种方案，仅额外消耗一份图副本的内存。

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