无重复遍历路径的水管网络节点13累计水量计算问题

现有一个有向水管网络：节点代表房屋，边代表连接房屋的管道，每条边带有水量属性。目标是计算最终到达节点13的总水量，正确结果为 5+2+1+6+0+3+14+4+12+5+8+10+6+9=85。

原代码问题 #

尝试用以下代码实现时，会出现重复计算边权重的问题（比如节点1到2的权重5会在1→2、1→2→5、1→2→5→6等多条路径中被多次求和），导致结果错误：

import networkx as nx
from itertools import combinations

G = nx.DiGraph()

edges = [(1,2,5), (2,5,0), (3,2,2), (3,4,1), (4,5,6), (5,6,3), (7,8,14), (8,6,4), (6,9,12), (9,11,8), (10,9,5),(10,12,10), (11,12,6),(12,13,9)]

for edge in edges:
    n1, n2, weight = edge 
    G.add_edge(n1, n2, volume=weight)

for n1, n2 in combinations(G.nodes,2):
    paths = list(nx.all_simple_paths(G=G, source=n1, target=n2))
    for path in paths:
        total_weight = nx.path_weight(G=G, path=path, weight="volume")
        print(f"From node {n1} to {n2}, there's the path {'-'.join([str(x) for x in path])} \n with the total volume: {total_weight}")

原代码的核心问题是：它遍历所有节点对的路径并计算路径总水量，但每条管道的水量只会被输送一次，不会因为属于多条路径就重复计算，因此不需要遍历所有路径。

解决方案 #

直接求和（适用于所有边都流向13的场景）

观察网络结构可知，所有管道的水量最终都会流向节点13，因此直接累加所有边的volume属性即可：

import networkx as nx

G = nx.DiGraph()

edges = [(1,2,5), (2,5,0), (3,2,2), (3,4,1), (4,5,6), (5,6,3), (7,8,14), (8,6,4), (6,9,12), (9,11,8), (10,9,5),(10,12,10), (11,12,6),(12,13,9)]

for edge in edges:
    n1, n2, weight = edge 
    G.add_edge(n1, n2, volume=weight)

# 累加所有边的水量
total_volume = sum(data['volume'] for _, _, data in G.edges(data=True))
print(f"到达节点13的总水量: {total_volume}")  # 输出85

严谨验证版（适用于可能存在无效边的场景）

如果网络中可能存在无法流向13的边，可以先筛选出所有能到达13的节点，再累加这些节点之间的边水量：

import networkx as nx

G = nx.DiGraph()

edges = [(1,2,5), (2,5,0), (3,2,2), (3,4,1), (4,5,6), (5,6,3), (7,8,14), (8,6,4), (6,9,12), (9,11,8), (10,9,5),(10,12,10), (11,12,6),(12,13,9)]

for edge in edges:
    n1, n2, weight = edge 
    G.add_edge(n1, n2, volume=weight)

# 获取所有能到达节点13的节点
nodes_reaching_13 = {node for node in G.nodes if nx.has_path(G, node, 13)}

# 筛选有效边并求和
total_volume = sum(
    data['volume'] 
    for u, v, data in G.edges(data=True) 
    if u in nodes_reaching_13 and v in nodes_reaching_13
)
print(f"到达节点13的总水量: {total_volume}")  # 输出85

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