Python訪問街區(qū)所有節(jié)點最短路徑問題，并結合matplotlib可視化

• • 1. 效果圖
  • 2. 源碼
  • • 2.1 5個點全排列（遞歸+非遞歸算法）
    • 2.2 python遍歷全路徑計算距離+matplot可視化
    • 2.3 pyecharts可視化源碼
  • 參考

寫這篇博客 基于博友的提問，這篇博客將介紹如何全排列街區(qū)的點，即規(guī)定起點不重復的走完所有街區(qū)，并找出最短路徑。

這個問題分拆分為三部分：

1. N個點除去起點，即N-1個點全排列；
2. 計算每一條路徑，相鄰節(jié)點的距離，并求和。
3. 為了更加直觀，便于可視化，可以matplotlib、pyecharts繪制路線出來~

1. 效果圖

規(guī)定起點A，所有路徑 遞歸 & 非遞歸效果圖：

最短路徑，及其距離效果圖：

圖中10個點的最短路徑結果：

使用matplotlib 可視化街區(qū)點及最短路徑如下圖：
如上最短路徑 A B D F G H I J E C 如下圖，

使用pyecharts繪制街區(qū)點及最短路徑如下圖：

2. 源碼

2.1 5個點全排列（遞歸+非遞歸算法）

非遞歸的方法并不好，當點數(shù)有變化的時候需要對應修改代碼

# 求最短路徑問題(N個點全排列）# 街區(qū)點
node = ['A', 'B', 'C', 'D', 'E']# 路徑全排列走法
count = 0
# 非遞歸算法
# 非遞歸算法找到所有可能的路徑,并計算總距離
for i in node:for j in node:for k in node:for m in node:for n in node:if i != 'A':  # 起點只能是A點continue# 同一個點不走第二次if (i == j or i == k or i == m or i == nor j == k or j == m or j == nor k == m or k == nor m == n):continuecount = count + 1print((count), (i, j, k, m, n))print('遞歸 start--------------------')
# 遞歸方法解決
nodes = node.copy()# 遞歸算法:
# 不重復的對n個點進行全排列
# positon，從數(shù)組下標哪個點開始全排列
def permutations(position):if position == len(nodes) - 1:print(nodes)else:for index in range(position, len(nodes)):nodes[index], nodes[position] = nodes[position], nodes[index]permutations(position + 1)nodes[index], nodes[position] = nodes[position], nodes[index]# permutations(0) # 全排列
permutations(1)  # 從第2個點開始全排列

2.2 python遍歷全路徑計算距離+matplot可視化

# 求最短路徑問題（python遍歷全路徑計算距離+matplot可視化）
import math
import numpy as np# 街區(qū)點
node = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', "J"]
# 街區(qū)點對應坐標
node_coor = [(310, 385), (360, 305), (550, 330), (440, 270), (550, 250),(360, 225), (305, 150), (305, 90), (440, 120), (550, 65)]# 計算倆個坐標點的距離
def cal_dis(pt1, pt2):x0, y0 = pt1x1, y1 = pt2# print('\t\tdis: ', pt1, pt2, math.sqrt((math.pow((x0 - x1), 2) + math.pow((y0 - y1), 2))))return math.sqrt((math.pow((x0 - x1), 2) + math.pow((y0 - y1), 2)))# 計算一條路徑的總距離
def get_dis(nodes):# 初始化總距離total_dis = 0# 遍歷路徑for i in range(len(nodes) - 1):# 根據(jù)相鄰的倆個點計算距離dis = cal_dis(node_coor[node.index(nodes[i])], node_coor[node.index(nodes[i + 1])])total_dis = total_dis + disreturn total_disprint('遞歸 start--------------------')
# 遞歸方法解決
dict_path_dis = {}
nodes = node.copy()# 遞歸算法:
# 不重復的對n個點進行全排列
# positon，從數(shù)組下標哪個點開始全排列
def permutations(position):if position == len(nodes) - 1:dis = get_dis(np.array(tuple(nodes)))dict_path_dis[tuple(nodes)] = disprint(tuple(nodes), dis)else:for index in range(position, len(nodes)):nodes[index], nodes[position] = nodes[position], nodes[index]permutations(position + 1)nodes[index], nodes[position] = nodes[position], nodes[index]# 從下標1開始全排列，表示第一個值是固定的，此處是起點
permutations(1)print('共有路徑: ', len(dict_path_dis.keys()))
# 獲取最小的value對應的key，即獲取最短路徑距離對應的路徑
key_min = min(dict_path_dis.keys(), key=(lambda k: dict_path_dis[k]))
print('遞歸——Minimum path & dis: ', key_min, dict_path_dis[key_min])print('繪圖start——————————')
# 構建最短路徑的街區(qū)點及坐標
min_node = np.array(key_min)
min_path_coor = []
for i in min_node:min_path_coor.append(node_coor[node.index(i)])print('min_node: ', min_node)
print('min_path_coor: ', min_path_coor)import matplotlib.pyplot as plt
import numpy as npfig, ax = plt.subplots()  # 創(chuàng)建一個圖表
x1 = [x for (x, y) in min_path_coor]
y1 = [y for (x, y) in min_path_coor]
# ax.scatter(x1, y1, marker='*', c='red') # 繪制街區(qū)點for node_name, (x, y) in zip(min_node, min_path_coor):# 繪制坐標點及坐標點上方文字plt.scatter(x, y, s=120, c='red', marker='*')plt.text(x=x, y=y + 2, s=node_name + '(' + str(x) + ',' + str(y) + ')', ha='center', va='baseline',fontdict={'color': 'black','size': 8})  # 中心點上方文字
ax.plot(x1, y1)  # 繪制線plt.show()

2.3 pyecharts可視化源碼

可在該頁面復制下方代碼進行在線可視化：https://echarts.apache.org/examples/en/editor.html?c=graph-simple

option = {title: {text: 'Graph 簡單示例'},tooltip: {},animationDurationUpdate: 1500,animationEasingUpdate: 'quinticInOut',series: [{type: 'graph',layout: 'none',symbolSize: 50,roam: true,label: {show: true},edgeSymbol: ['circle', 'arrow'],edgeSymbolSize: [4, 10],edgeLabel: {fontSize: 20},data: [{name: '節(jié)點A',x: 310,y: 385}, {name: '節(jié)點B',x: 360,y: 305}, {name: '節(jié)點C',x: 550,y: 330}, {name: '節(jié)點D',x: 440,y: 270}, {name: '節(jié)點E',x: 550,y: 250}, {name: '節(jié)點F',x: 360,y: 225}, {name: '節(jié)點G',x: 305,y: 150}, {name: '節(jié)點H',x: 305,y: 90}, {name: '節(jié)點I',x: 440,y: 120}, {name: '節(jié)點J',x: 550,y: 65}],links: [{source: '節(jié)點A',target: '節(jié)點B'}, {source: '節(jié)點B',target: '節(jié)點D'}, {source: '節(jié)點D',target: '節(jié)點F'}, {source: '節(jié)點F',target: '節(jié)點G'}, {source: '節(jié)點G',target: '節(jié)點H'}, {source: '節(jié)點H',target: '節(jié)點I'}, {source: '節(jié)點I',target: '節(jié)點J'}, {source: '節(jié)點J',target: '節(jié)點E'}, {source: '節(jié)點E',target: '節(jié)點C'}],lineStyle: {opacity: 0.9,width: 2,curveness: 0}}]
};

參考

• python實現(xiàn)四個數(shù)字的全排列

總結

以上是生活随笔為你收集整理的Python访问街区所有节点最短路径问题，并结合matplotlib可视化的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。