如何在NetworkX图中获取指定节点的TSP近似最优顺序与最小距离

你调用networkx.approximation.traveling_salesman_problem未得到优化路径的核心原因有两个：

• 传入的nodes列表存在重复节点（A0_S14_R4累计出现3次），NetworkX的TSP实现默认会先对传入的节点列表去重后再执行路径规划，重复节点会干扰优化逻辑
• 未显式指定权重参数时，函数不会自动计算非完全图中节点对的最短路径作为距离依据，导致优化逻辑未生效

正确实现步骤 #

步骤1：预处理目标节点 #

先对需要访问的节点去重，得到唯一的待访问节点列表：

target_nodes = ['A0_S0_R0', 'A0_S14_R4', 'A0_S4_R4', 'A0_S14_R4', 'A0_S14_R4', 'A0_S7_R4']
# 去重保留唯一访问节点
unique_nodes = list(set(target_nodes))

步骤2：调用TSP近似算法获取最优路径 #

调用函数时显式指定边权重字段、是否需要生成闭环：

import networkx as nx

optimized_order = nx.approximation.traveling_salesman_problem(
    DS.G,
    nodes=unique_nodes,
    weight='weight', # 替换为你图中边对应的距离字段名称
    cycle=False # 不需要回到起点设为False，需要闭环回到起点设为True
)

步骤3：计算最小总出行距离 #

累加最优路径相邻节点的最短路径长度，得到总距离：

total_distance = 0
for i in range(len(optimized_order)-1):
    total_distance += nx.shortest_path_length(
        DS.G, 
        optimized_order[i], 
        optimized_order[i+1], 
        weight='weight'
    )

print("最优节点访问顺序：", optimized_order)
print("最小总出行距离：", total_distance)

补充说明 #

如果去重后的待访问节点数量≤10，可以直接暴力枚举所有排列得到精确最优解，无需使用近似算法，精度更高。
如果有重复访问节点的业务需求，在得到最优访问顺序后，按需求插入重复节点即可，重复访问同一节点不会额外增加出行距离。

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