Networkx库的学习历程：旅行商问题
6 min read
Page Views
1.原始数据
各地点之间的距离数据如下所示：
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 23 54 55 26
2 23 56 18
3 56 50 44 61
4 50 28 27
5 54 18 44 51 34 56 48
6 61 28 51 27 42
7 55 34 36 38
8 56 36 29 33
9 48 27 29 61 29 42 36
10 27 42 61 25
11 26 24
12 38 33 29 24 30
13 42 30 47
14 36 25 47
2.python程序
import numpy as np
import pandas as pd
from scipy.sparse import coo_matrix
import networkx as nx
import matplotlib.pyplot as plt
"""
numpy: 1.24.3
pandas: 1.5.3
networkx: 3.1
matplotlib: 3.7.5
"""
# 避免图片无法显示中文
plt.rcParams['font.sans-serif'] = ['SimHei']
# 显示所有列
pd.set_option('display.max_columns', None)
pd.set_option('display.width', 1000)
# 读取数据
dataframe = pd.read_excel(io='数据.xlsx', sheet_name='Sheet1', index_col=0)
dataframe = dataframe.fillna(0)
print('矩阵的空值以0填充：\n', dataframe)
coo = coo_matrix(np.array(dataframe))
# 矩阵行列的索引默认从0开始改成从1开始
coo.row += 1
coo.col += 1
data = [int(i) for i in coo.data]
coo_tuple = list(zip(coo.row, coo.col, data))
coo_list = []
for i in coo_tuple:
coo_list.append(list(i))
# 出发点
start_node = 1
# 目的地
target_node = 14
# 设置各顶点坐标（只是方便绘图，并不是实际位置）
pos = {1: (1, 8), 2: (4, 10), 3: (11, 11), 4: (14, 8), 5: (5, 7), 6: (10, 6), 7: (3, 5), 8: (6, 4), 9: (8, 4),
10: (14, 5), 11: (2, 3), 12: (5, 1), 13: (8, 1), 14: (13, 3)}
# 创建空的无向图
G = nx.Graph()
# 给无向图的边赋予权值
G.add_weighted_edges_from(coo_list)
# 旅行商问题算法：
# christofides：适合无向图，不适合有向图
# greedy_tsp：无向图、有向图均适合
# simulated_annealing_tsp：无向图、有向图均适合
# threshold_accepting_tsp：无向图、有向图均适合
# asadpour_atsp：不适合无向图，适合有向图
def draw_tsp(name, tsp):
tsp_edges = [[tsp[i], tsp[i + 1]] for i in range(len(tsp) - 1)]
tsp_length = sum(d for i in range(len(tsp) - 1) for (s, e, d) in coo_list if (s, e) == (tsp[i], tsp[i + 1]))
print(f'\n基于{name}算法的旅行商路线：%s，总里程：%d' % (tsp, tsp_length))
plt.figure()
plt.suptitle(f'基于{name}算法的旅行商路线图')
# 绘制无向加权图
nx.draw(G, pos, with_labels=True)
# 显示无向加权图的边的权值
labels = nx.get_edge_attributes(G, name='weight')
# 设置顶点颜色
nx.draw_networkx_nodes(G, pos, node_color='yellow', edgecolors='red')
nx.draw_networkx_nodes(G, pos, nodelist=[start_node], node_color='#00ff00', edgecolors='red')
# 设置边颜色和宽度
nx.draw_networkx_edges(G, pos, edgelist=tsp_edges, edge_color='blue', width=5, arrows=True, arrowstyle='->',
arrowsize=15)
# 显示边的权值
nx.draw_networkx_edge_labels(G, pos, edge_labels=labels, font_color='purple', font_size=10)
draw_tsp(name='Christofides', tsp=nx.approximation.traveling_salesman_problem(G, method=nx.approximation.christofides))
draw_tsp(name='Greedy', tsp=nx.approximation.traveling_salesman_problem(G, method=nx.approximation.greedy_tsp))
draw_tsp(name='Simulated Annealing', tsp=nx.approximation.traveling_salesman_problem(G, method=lambda G,
weight: nx.approximation.simulated_annealing_tsp(
G, init_cycle=list(G) + [next(iter(G))], weight=weight, max_iterations=500, N_inner=200)))
draw_tsp(name='Threshold Accepting', tsp=nx.approximation.traveling_salesman_problem(G, method=lambda G,
weight: nx.approximation.threshold_accepting_tsp(
G, init_cycle=list(G) + [next(iter(G))], weight=weight, max_iterations=500, N_inner=200)))
plt.show()
3.效果展示
矩阵的空值以0填充：
1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 0.0 23.0 0.0 0.0 54.0 0.0 55.0 0.0 0.0 0.0 26.0 0.0 0.0 0.0
2 23.0 0.0 56.0 0.0 18.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
3 0.0 56.0 0.0 50.0 44.0 61.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0
4 0.0 0.0 50.0 0.0 0.0 28.0 0.0 0.0 0.0 27.0 0.0 0.0 0.0 0.0
5 54.0 18.0 44.0 0.0 0.0 51.0 34.0 56.0 48.0 0.0 0.0 0.0 0.0 0.0
6 0.0 0.0 61.0 28.0 51.0 0.0 0.0 0.0 27.0 42.0 0.0 0.0 0.0 0.0
7 55.0 0.0 0.0 0.0 34.0 0.0 0.0 36.0 0.0 0.0 0.0 38.0 0.0 0.0
8 0.0 0.0 0.0 0.0 56.0 0.0 36.0 0.0 29.0 0.0 0.0 33.0 0.0 0.0
9 0.0 0.0 0.0 0.0 48.0 27.0 0.0 29.0 0.0 61.0 0.0 29.0 42.0 36.0
10 0.0 0.0 0.0 27.0 0.0 42.0 0.0 0.0 61.0 0.0 0.0 0.0 0.0 25.0
11 26.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 24.0 0.0 0.0
12 0.0 0.0 0.0 0.0 0.0 0.0 38.0 33.0 29.0 0.0 24.0 0.0 30.0 0.0
13 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 42.0 0.0 0.0 30.0 0.0 47.0
14 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 36.0 25.0 0.0 0.0 47.0 0.0
基于Christofides算法的旅行商路线：[1, 11, 12, 13, 9, 14, 10, 4, 6, 9, 8, 7, 5, 3, 2, 1]，总里程：487
基于Greedy算法的旅行商路线：[1, 2, 5, 7, 8, 9, 6, 4, 10, 14, 13, 12, 11, 1, 2, 3, 2, 1]，总里程：532
基于Simulated Annealing算法的旅行商路线：[1, 2, 1, 11, 12, 8, 12, 13, 9, 14, 10, 4, 6, 3, 5, 7, 1]，总里程：544
基于Threshold Accepting算法的旅行商路线：[1, 2, 3, 5, 7, 8, 12, 13, 9, 6, 4, 10, 14, 9, 12, 11, 1]，总里程：520
Last updated on 2025-05-24