Python 3+NetworkX 1.11加权图最短路径未计算节点权重咨询

Hey Sam, great question! The issue here is that NetworkX's default shortest path algorithms (like Dijkstra's) only account for edge weights by default—they don't automatically include node weights in the total path cost. Let's walk through two solid approaches to fix this, using your Python 3 and NetworkX 1.11 setup.

方法1：将节点权重合并到相邻边权重 #

This approach folds node weights into the edges connected to the node, so standard shortest path functions can account for them. You can adjust the logic based on whether you need to include start/end node weights.

假设你的原始图是这样构建的（节点和边的权重都存在weight属性中）：

import networkx as nx

# 初始化有向图（无向图用nx.Graph()即可）
G = nx.DiGraph()
# 添加带权重的节点
G.add_nodes_from([1, 2, 3], weight=[10, 20, 30])
# 添加带权重的边
G.add_edges_from([(1, 2, {'weight': 5}), (2, 3, {'weight': 7})])

我们把每个节点的权重加到它的出边上，路径计算时会自动包含节点权重，最后再加上终点的权重（如果需要）：

# 创建新图，存储合并后的边权重
G_combined = nx.DiGraph()

for u, v, edge_attrs in G.edges(data=True):
    # 取出原边权重，默认1如果未设置
    edge_weight = edge_attrs.get('weight', 1)
    # 合并节点u的权重到边权重
    total_edge_weight = edge_weight + G.nodes[u]['weight']
    G_combined.add_edge(u, v, weight=total_edge_weight)

# 计算最短路径
shortest_path = nx.shortest_path(G_combined, source=1, target=3, weight='weight')
# 计算路径的边权重总和
path_edge_total = nx.shortest_path_length(G_combined, source=1, target=3, weight='weight')
# 加上终点的权重（如果需要包含终点）
total_path_weight = path_edge_total + G.nodes[shortest_path[-1]]['weight']

print(f"最短路径: {shortest_path}")
print(f"总权重（含节点）: {total_path_weight}")  # 输出72，对应10+5+20+7+30

方法2：拆分节点为"In"和"Out"节点（更通用） #

This method gives you precise control over which nodes are included (start, middle, end). We split each original node into two: an "in" node and an "out" node. The edge between them carries the original node's weight, and original edges are redirected to connect the out node of one to the in node of the next.

import networkx as nx

# 使用和之前一致的原始图G
G = nx.DiGraph()
G.add_nodes_from([1, 2, 3], weight=[10, 20, 30])
G.add_edges_from([(1, 2, {'weight': 5}), (2, 3, {'weight': 7})])

# 创建拆分后的图
G_split = nx.DiGraph()

for node in G.nodes():
    # 添加节点的in->out边，权重为原节点的权重
    node_in = f"{node}_in"
    node_out = f"{node}_out"
    G_split.add_edge(node_in, node_out, weight=G.nodes[node]['weight'])
    
    # 重定向原边：原边u->v变成u_out -> v_in，权重保留原边权重
    for neighbor in G.neighbors(node):
        edge_weight = G[node][neighbor].get('weight', 1)
        G_split.add_edge(node_out, f"{neighbor}_in", weight=edge_weight)

# 计算路径：从起点的in节点到终点的out节点
source_in = "1_in"
target_out = "3_out"
shortest_split_path = nx.shortest_path(G_split, source=source_in, target=target_out, weight='weight')
total_split_weight = nx.shortest_path_length(G_split, source=source_in, target=target_out, weight='weight')

print(f"拆分后的路径: {shortest_split_path}")
print(f"总权重（含所有节点）: {total_split_weight}")  # 同样输出72

关键说明 #

• 方法1更简洁，但需要根据需求调整是否包含起点/终点权重；
• 方法2更通用，适合复杂场景（比如部分节点不需要计入权重，或对节点权重计算有特殊规则）；
• 如果是无向图，只需把nx.DiGraph()换成nx.Graph()，其余逻辑基本一致。

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