基于NetworkX的Christofides TSP算法：筛选最远起止节点的解

1. 处理Christofides算法的返回结果 #

NetworkX的nx.approximation.christofides返回的是循环路径列表，格式为[节点1, 节点2, ..., 节点N, 节点1]——遍历所有节点后回到起点。我们先提取不含重复起点的核心循环序列：

import networkx as nx

# 假设已构建无向带权图G
tsp_cycle = nx.approximation.christofides(G)
# 提取核心循环节点（去掉最后重复的起点）
core_cycle = tsp_cycle[:-1]
n = len(core_cycle)

2. 生成所有起始节点变体 #

每个变体对应从核心循环的不同节点开始，按原顺序遍历所有节点后回到起点。通过切片快速生成所有变体：

variants = []
for i in range(n):
    # 生成从第i个节点起始的循环变体
    variant = core_cycle[i:] + core_cycle[:i] + [core_cycle[i]]
    variants.append(variant)

3. 筛选起止距离最大的变体 #

这里的“起止节点距离”指变体线性部分的起点（第一个节点）与倒数第二个节点（循环回到起点前的最后一个节点）之间的边权。遍历所有变体，找出距离最大的那个：

max_distance = -1
best_variant = None

for variant in variants:
    start = variant[0]
    end = variant[-2]
    # 获取无向图中两点的边权
    distance = G.get_edge_data(start, end)['weight']
    if distance > max_distance:
        max_distance = distance
        best_variant = variant

4. 输出结果 #

最终的best_variant就是符合要求的TSP解变体，可直接用于后续计算或输出。

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