如何对NetworkX图的边权重求和？最短路径权重计算方法

核心认知澄清 #

很多人刚开始用NetworkX的时候会有一个误区：以为拿到最短路径的节点列表后，必须自己遍历累加边的权重才能得到路径总长度，实际上这个功能NetworkX早就内置了：

• 你当前代码中已经使用的nx.shortest_path_length，已经内置了权重求和逻辑，只要图的边携带weight属性，该函数返回的结果就是路径的总权重和，不需要额外手动计算
• 你通过G.add_weighted_edges_from()添加的边，权重会自动存储在边的weight属性中，完全匹配NetworkX最短路径算法的默认权重识别规则

需要注意：nx.shortest_path_length的默认行为，是优先识别边中的weight属性作为计算权重，只有当边没有该属性时，才会按每边长度为1计算跳数长度。也就是说你现在代码里打印的shortest_value、标注为distance的数值，本身就是目标最短路径的边权重累加结果，不是无意义的节点跳数。

你现有代码的逻辑参考 #

import matplotlib.pyplot as plt
import networkx as nx

def graph(path):
    G = nx.Graph()
    for line in open(path):
        strlist = line.split(',')
        n1 = strlist[0].replace('.0', '')
        n2 = strlist[1].replace('.0', '')
        weight = round(float(strlist[2]), 2)
        G.add_weighted_edges_from([(n1, n2, weight)])

    elarge = [(u, v) for (u, v, d) in G.edges(data=True) if d["weight"] > 0.5]
    esmall = [(u, v) for (u, v, d) in G.edges(data=True) if d["weight"] <= 0.5]
    pos = nx.spring_layout(G)
    nx.draw_networkx_nodes(G, pos, node_size=200, node_color='#ff0000', alpha=0.9)
    nx.draw_networkx_edges(G, pos, edgelist=elarge, width=1, edge_color='b', alpha=0.05)
    nx.draw_networkx_edges(G, pos, edgelist=esmall, width=1, edge_color='b', alpha=0.3)
    edge_labels = nx.get_edge_attributes(G, 'weight')
    nx.draw_networkx_labels(G, pos, font_size=10, font_family="sans-serif")
    nx.draw_networkx_edge_labels(G, pos, edge_labels, font_size=8, font_family='sans-serif')
    plt.axis("off")
    plt.show()
    return G

G = graph('graph.csv')

# 该函数默认读取边的weight属性，返回值就是最短路径的总权重和
shortest_value = nx.shortest_path_length(G, source='210', target='2771')
print(shortest_value)
# 该函数返回值是最短路径的节点序列
shortest_path = nx.shortest_path(G, source='210', target='2771', method='dijkstra')
print('shortest path：{}'.format(shortest_path))
print('distance：{}'.format(shortest_value))

手动累加路径权重的适用场景 #

如果遇到以下情况，你可以手动遍历路径计算权重总和：

• 需要对一段非NetworkX计算出来的自定义路径计算总权重
• 需要验证算法计算出的最短路径的权重结果是否正确

手动计算的实现示例：

# 输入为节点构成的路径列表，比如['210', '105', '432', '2771']
def get_path_total_weight(G, path):
    total = 0
    # 遍历路径中每一对相邻节点
    for u, v in zip(path[:-1], path[1:]):
        # 读取边存储的weight属性值并累加
        total += G.edges[u, v]['weight']
    return total

# 调用示例
path_weight_sum = get_path_total_weight(G, shortest_path)
print(f'手动计算的路径总权重：{path_weight_sum}')

常见易踩坑点 #

• 如果你自定义的边权重属性名不是weight（比如命名为cost、distance），调用最短路径相关函数时需要显式指定weight='你的属性名'参数，否则函数会默认忽略权重，按节点间的跳数计算长度
• 无向图读取边属性时不需要考虑节点顺序，无论传入(u,v)还是(v,u)，都能正常读取到对应的边权重值

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