如何使用NetworkX求解节点值为权重的两节点最短路径

NetworkX内置最短路径接口默认基于边权重计算，没有直接提供节点权重的计算入口，只需要把节点数值按规则折算为边权重，就可以直接调用内置算法实现需求，不需要自己手写路径搜索逻辑。

方法1：无向图直接折算（无需改动图结构） #

核心逻辑：给每条无向边的权重赋值为边两端节点的数值之和，计算出边权最短路径后，通过固定公式换算为节点权重总和，全程保留原有无向图结构。
折算公式：路径节点总权重 = (路径边权总和 + 起点数值 + 终点数值) // 2
完整代码示例：

import networkx as nx

# 原有建图逻辑
G = nx.Graph()
G.add_edges_from([(10, 20), (20, 30), (10, 30)]) # 可替换为你自己的加边逻辑

# 批量给所有边赋值权重
for u, v in G.edges():
    G[u][v]['weight'] = u + v

def get_min_node_path(G, source, target):
    # 调用内置Dijkstra算法获取最短路径和对应边权总和
    path, edge_weight_sum = nx.single_source_dijkstra(G, source, target, weight='weight')
    # 换算为节点权重总和
    node_weight_sum = (edge_weight_sum + source + target) // 2
    return path, node_weight_sum

# 测试
path, total_weight = get_min_node_path(G, 10, 30)
print(path) # 输出 [10, 30]
print(total_weight) # 输出 40，即10+30=40，符合预期

方法2：转有向图赋值（逻辑更直观） #

核心逻辑：把原有无向图转为有向图，每条无向边拆成两个方向的有向边，边权等于边指向的目标节点的数值。最终边权总和加上起点的数值，就是整条路径所有途经节点的数值和，不需要额外记换算公式。
完整代码示例：

import networkx as nx

# 原有建图逻辑
G = nx.Graph()
G.add_edges_from([(10, 20), (20, 30), (10, 30)]) # 可替换为你自己的加边逻辑

# 转换为有向图并赋值边权
DiG = nx.DiGraph()
for u, v in G.edges():
    DiG.add_edge(u, v, weight=v) # u到v的权重为目标节点v的数值
    DiG.add_edge(v, u, weight=u) # v到u的权重为目标节点u的数值

def get_min_node_path(DiG, source, target):
    path, edge_weight_sum = nx.single_source_dijkstra(DiG, source, target, weight='weight')
    # 边权总和已经包含除起点外所有节点的数值，加上起点值即可
    node_weight_sum = edge_weight_sum + source
    return path, node_weight_sum

# 测试
path, total_weight = get_min_node_path(DiG, 10, 30)
print(path) # 输出 [10, 30]
print(total_weight) # 输出 40，结果一致

注意事项 #

• 两种方法都支持非负节点值的场景，和NetworkX内置的Dijkstra、A*等最短路径算法完全兼容。
• 如果后续需要给节点设置独立于节点id的权重值，只需要提前给节点添加对应属性（比如G.nodes[node]['cost'] = 自定义权重），边权赋值时读取对应属性即可，逻辑不需要改动。
• 如果你只需要路径不需要总权重，直接调用nx.dijkstra_path即可，不用做权重换算。

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