networkx无向图中求解需经过多个中间关键节点的最短路径

实现思路 #

你的需求本质是带固定起点终点的旅行商（TSP）问题变种，核心实现逻辑适配无向图非常简单：

1. 先把源节点、所有必须经过的中间节点、目标节点统一归类为关键节点
2. 预计算所有关键节点两两之间的最短路径和对应权重，networkx会自动适配你构造的nx.Graph()无向图特性，无需额外调整
3. 枚举中间节点的所有排列，找到总权重最小的遍历顺序，节点数量多时可以用近似TSP算法降低计算量
4. 按最优顺序拼接各段最短路径，得到最终完整路径

代码实现 #

方案1：穷举排列（适合中间节点≤10个的场景，结果精确） #

from itertools import permutations

# 替换为你自己的参数
source = 2001
target = 406008
must_pass = [xxx, xxx, xxx] # 填写你的必须经过的中间节点列表

# 收集所有关键节点
key_nodes = [source] + must_pass + [target]
# 预计算关键节点两两之间的最短距离和路径
dist_map = {}
path_map = {}
for u in key_nodes:
    for v in key_nodes:
        if u == v:
            dist_map[(u, v)] = 0
            path_map[(u, v)] = [u]
            continue
        # 适配你的边权字段weight
        dist_map[(u, v)] = nx.shortest_path_length(G, u, v, weight='weight')
        path_map[(u, v)] = nx.shortest_path(G, u, v, weight='weight')

# 枚举所有中间节点的排列，找总权重最小的
min_total_weight = float('inf')
best_order = None
for perm in permutations(must_pass):
    current_weight = dist_map[(source, perm[0])]
    for i in range(len(perm)-1):
        current_weight += dist_map[(perm[i], perm[i+1])]
    current_weight += dist_map[(perm[-1], target)]
    if current_weight < min_total_weight:
        min_total_weight = current_weight
        best_order = perm

# 拼接最终完整路径
final_path = path_map[(source, best_order[0])]
for i in range(len(best_order)-1):
    # 去掉重复的节点
    final_path += path_map[(best_order[i], best_order[i+1])][1:]
final_path += path_map[(best_order[-1], target)][1:]

print("最短路径总权重：", min_total_weight)
print("最短路径节点序列：", final_path)

方案2：TSP近似求解（适合中间节点>10个的场景，运算速度快） #

# 收集所有关键节点
source = 2001
target = 406008
must_pass = [xxx, xxx, xxx]
key_nodes = [source] + must_pass + [target]

# 构造关键节点的完全图，边权为原图中两点的最短路径权重
complete_g = nx.Graph()
for idx_u, u in enumerate(key_nodes):
    for v in key_nodes[idx_u+1:]:
        d = nx.shortest_path_length(G, u, v, weight='weight')
        complete_g.add_edge(u, v, weight=d)

# 调用近似TSP求解，指定不生成环、固定起点
tsp_node_order = nx.approximation.traveling_salesman_problem(
    complete_g, 
    nodes=key_nodes, 
    cycle=False, 
    source=source
)

# 拼接原路径
final_path = []
for i in range(len(tsp_node_order)-1):
    u, v = tsp_node_order[i], tsp_node_order[i+1]
    seg_path = nx.shortest_path(G, u, v, weight='weight')
    final_path += seg_path if i == 0 else seg_path[1:]

print("近似最短路径节点序列：", final_path)

注意事项 #

• 运行前请确保所有关键节点（源、目标、中间必须经过节点）在图中是互相连通的，否则最短路径计算会报错
• 若不需要按边权计算，仅按路径节点数算最短路径，去掉所有weight='weight'参数即可

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