#========第一步：導(dǎo)入相關(guān)庫==================
import pandas as pd
import numpy as np
import math
import time
?
#======第二步：讀取數(shù)據(jù)=================
dataframe = pd.read_csv("旅行商問題.csv", sep=",", header=None)
v = dataframe.iloc[:, 1:3] ? ? ?#去除第一列12345678910,只保留x,y
print('讀取數(shù)據(jù):----------------------------')
print(v)
?
#=======第三步：計算城市之間的距離========
train_v= np.array(v)
train_d=train_v
dist = np.zeros((train_v.shape[0],train_d.shape[0])) ? ?#初始化距離 為10*10的全0矩陣
print(dist.shape) ? ?#(10,10)
?
#==計算距離矩陣===
for i in range(train_v.shape[0]):
? ? for j in range(train_d.shape[0]):
? ? ? ? dist[i,j] = math.sqrt(np.sum((train_v[i,:]-train_d[j,:])**2))
print('距離矩陣:----------------------------------')
print(dist)
?
#==========第四步：計算距離和路徑==============
"""
s:已經(jīng)遍歷過的城市
dist：城市間距離矩陣
sumpath:目前的最小路徑總長度
Dtemp：當(dāng)前最小距離
flag：訪問標記
"""
i=1
n=train_v.shape[0]#城市個數(shù)
j=0
sumpath=0#目前的最小路徑總長度
s=[]#已經(jīng)遍歷過的城市
s.append(0)#從城市0開始
start = time.perf_counter() ? ? #time.clock()
while True:
? ? k=1#從1開始,因為人在城市0，所以我們設(shè)定先從城市1開始選擇
? ? Detemp=float('inf')#當(dāng)前最小距離
? ? while True:
? ? ? ? flag=0#訪問標記，否0
? ? ? ? if k in s:#是否訪問，如果訪問過，flag設(shè)為1
? ? ? ? ? ? flag = 1
? ? ? ? if (flag==0) and (dist[k][s[i-1]] < Detemp):#如果未訪問過，并且距離小于最小距離
? ? ? ? ? ? j = k;
? ? ? ? ? ? Detemp=dist[k][s[i - 1]]; ? ? #當(dāng)前兩座城市相鄰距離
? ? ? ? k+=1#遍歷下一城市
? ? ? ? if k>=n:
? ? ? ? ? ? break;
? ? s.append(j)
? ? i+=1;
? ? sumpath+=Detemp
? ? if i>=n:
? ? ? ? break;
?
sumpath+=dist[0][j]#加上dist[0][j] 表示最后又回到起點
end = time.perf_counter() ? #time.clock()
print("距離：")
print(sumpath)
print('*--------------*')
print('路徑：')
for m in range(n):
? ? print("%s-> "%(s[m]),end='')
print()
print("程序的運行時間是：%s"%(end-start))

#==========創(chuàng)建圖================
?
import networkx as nx ?# 導(dǎo)入 NetworkX 工具包
G1 = nx.Graph() ?# 創(chuàng)建：空的 無向圖
G2 = nx.DiGraph() ?#創(chuàng)建：空的 有向圖
G3 = nx.MultiGraph() ?#創(chuàng)建：空的 多圖
G4 = nx.MultiDiGraph() ?#創(chuàng)建：空的 有向多圖

#================頂點的添加、刪除和查看=============
?
#======頂點(node)的操作=====
?
#==向圖中添加頂點==
G1.add_node(1) ?# 向 G1 添加頂點 1
G1.add_node(1, name='n1', weight=1.0) ?# 添加頂點 1，定義 name, weight 屬性
G1.add_node(2, date='May-16') # 添加頂點 2，定義 time 屬性
G1.add_nodes_from([3, 0, 6], dist=1) ?# 添加多個頂點，并定義屬性
G1.add_nodes_from(range(10, 15)) ?# 向圖 G1 添加頂點 10～14
?
#==查看頂點和頂點屬性==
print(G1.nodes()) ?# 查看頂點列表
# [1, 2, 3, 0, 6, 10, 11, 12, 13, 14]
print(G1._node) ?# 查看頂點屬性
# {1: {'name': 'n1', 'weight': 1.0}, 2: {'date': 'May-16'}, 3: {'dist': 1}, 0: {'dist': 1}, 6: {'dist': 1}, 10: {}, 11: {}, 12: {}, 13: {}, 14: {}}
?
#==從圖中刪除頂點==
G1.remove_node(1) ?# 刪除頂點
G1.remove_nodes_from([1, 11, 13, 14]) ?# 通過頂點標簽的 list 刪除多個頂點
print(G1.nodes()) ?# 查看頂點
# [2, 3, 0, 6, 10, 12] ?# 頂點列表

#====================邊的添加、刪除和查看================
?
#========邊(edge)的操作========
?
#==向圖中添加邊==
G1.add_edge(1,5) ?# 向 G1 添加邊，并自動添加圖中沒有的頂點
G1.add_edge(0,10, weight=2.7) ?# 向 G1 添加邊，并設(shè)置邊的屬性
G1.add_edges_from([(1,2,{'weight':0}), (2,3,{'color':'blue'})]) ?# 向圖中添加邊，并設(shè)置#==屬性==
G1.add_edges_from([(3,6),(1,2),(6,7),(5,10),(0,1)]) ?# 向圖中添加多條邊
G1.add_weighted_edges_from([(1,2,3.6),[6,12,0.5]]) ?# 向圖中添加多條賦權(quán)邊: (node1,node2,weight)
print(G1.nodes()) ?# 查看頂點
# [2, 3, 0, 6, 10, 12, 1, 5, 7] ?# 自動添加了圖中沒有的頂點
?
#==從圖中刪除邊==
G1.remove_edge(0,1) ?# 從圖中刪除邊 0-1
G1.remove_edges_from([(2,3),(1,5),(6,7)]) ?# 從圖中刪除多條邊
?
#==查看邊和邊的屬性==
print(G1.edges) ?# 查看所有的邊
[(2, 1), (3, 6), (0, 10), (6, 12), (10, 5)]
print(G1.get_edge_data(1,2)) ?# 查看指定邊的屬性
# {'weight': 3.6}
print(G1[1][2]) ?# 查看指定邊的屬性
# {'weight': 3.6}
print(G1.edges(data=True)) ?# 查看所有邊的屬性
# [(2, 1, {'weight': 3.6}), (3, 6, {}), (0, 10, {'weight': 2.7}), (6, 12, {'weight': 0.5}), (10, 5, {})]

#========導(dǎo)入相關(guān)包=========================
import matplotlib.pyplot as plt # 導(dǎo)入 Matplotlib 工具包
import networkx as nx ?# 導(dǎo)入 NetworkX 工具包
?
#======問題：無向圖的最短路問題===============
G1 = nx.Graph() ?# 創(chuàng)建：空的 無向圖
G1.add_weighted_edges_from([(1,2,2),(1,3,8),(1,4,1),
? ? ? ? ? ? ? ? ? ? ? ? ? ? (2,3,6),(2,5,1),
? ? ? ? ? ? ? ? ? ? ? ? ? ? (3,4,7),(3,5,5),(3,6,1),(3,7,2),
? ? ? ? ? ? ? ? ? ? ? ? ? ? (4,7,9),
? ? ? ? ? ? ? ? ? ? ? ? ? ? (5,6,3),(5,8,2),(5,9,9),
? ? ? ? ? ? ? ? ? ? ? ? ? ? (6,7,4),(6,9,6),
? ? ? ? ? ? ? ? ? ? ? ? ? ? (7,9,3),(7,10,1),
? ? ? ? ? ? ? ? ? ? ? ? ? ? (8,9,7),(8,11,9),
? ? ? ? ? ? ? ? ? ? ? ? ? ? (9,10,1),(9,11,2),
? ? ? ? ? ? ? ? ? ? ? ? ? ? (10,11,4)]) ?# 向圖中添加多條賦權(quán)邊: (node1,node2,weight)
print('nx.info:',G1.nodes) ?# 返回圖的基本信息,nx.info:返回圖的基本信息
?
#=======兩個指定頂點之間的最短加權(quán)路徑===============
minWPath_v1_v11 = nx.dijkstra_path(G1, source=1, target=11) ?# 頂點 1 到 頂點 11 的最短加權(quán)路徑
print("頂點 v1 到 頂點 v11 的最短加權(quán)路徑: ", minWPath_v1_v11)
# 兩個指定頂點之間的最短加權(quán)路徑的長度
lMinWPath_v1_v11 = nx.dijkstra_path_length(G1, source=1, target=11) ?# 最短加權(quán)路徑長度
print("頂點 v1 到 頂點 v11 的最短加權(quán)路徑長度: ", lMinWPath_v1_v11)
?
pos = {1: (0,4), 2: (5,7), 3: (5,4), 4: (5,1), 5: (10,7), 6: (10,4), 7: (10,1),
? ? ? ?8: (15,7), 9: (15,4), 10: (15,1), 11: (20,4)} ?# 指定頂點位置,以節(jié)點為鍵，位置為值的字典
labels = nx.get_edge_attributes(G1, 'weight') ?# 設(shè)置邊的 labels 為 ‘weight'
nx.draw(G1, pos,node_color = 'r',with_labels=True, font_color='b') ?# 繪制無向圖,pos 指的是布局
nx.draw_networkx_edge_labels(G1, pos, edge_labels=labels, font_color='y') ?# 顯示邊的權(quán)值
plt.show()