Python訪問街區所有節點最短路徑問題，并結合matplotlib可視化

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

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

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

1. 效果圖

規定起點A，所有路徑 遞回 & 非遞回效果圖：

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

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

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

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

2. 原始碼

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

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

# 求最短路徑問題(N個點全排列）

# 街區點
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 == n
                        or j == k or j == m or j == n
                        or k == m or k == n
                        or m == n):
                        continue
                    count = count + 1
                    print((count), (i, j, k, m, n))

print('遞回 start--------------------')
# 遞回方法解決
nodes = node.copy()


# 遞回演算法:
# 不重復的對n個點進行全排列
# positon，從陣列下標哪個點開始全排列
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

# 街區點
node = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', "J"]
# 街區點對應坐標
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 = pt1
    x1, 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):
        # 根據相鄰的倆個點計算距離
        dis = cal_dis(node_coor[node.index(nodes[i])], node_coor[node.index(nodes[i + 1])])
        total_dis = total_dis + dis
    return total_dis


print('遞回 start--------------------')
# 遞回方法解決
dict_path_dis = {}
nodes = node.copy()


# 遞回演算法:
# 不重復的對n個點進行全排列
# positon，從陣列下標哪個點開始全排列
def permutations(position):
    if position == len(nodes) - 1:
        dis = get_dis(np.array(tuple(nodes)))
        dict_path_dis[tuple(nodes)] = dis
        print(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——————————')
# 構建最短路徑的街區點及坐標
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 np

fig, ax = plt.subplots()  # 創建一個圖表
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') # 繪制街區點

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: '節點A',
                x: 310,
                y: 385
            }, {
                name: '節點B',
                x: 360,
                y: 305
            }, {
                name: '節點C',
                x: 550,
                y: 330
            }, {
                name: '節點D',
                x: 440,
                y: 270
            }, {
                name: '節點E',
                x: 550,
                y: 250
            }, {
                name: '節點F',
                x: 360,
                y: 225
            }, {
                name: '節點G',
                x: 305,
                y: 150
            }, {
                name: '節點H',
                x: 305,
                y: 90
            }, {
                name: '節點I',
                x: 440,
                y: 120
            }, {
                name: '節點J',
                x: 550,
                y: 65
            }],
            links: [{
                source: '節點A',
                target: '節點B'
            }, {
                source: '節點B',
                target: '節點D'
            }, {
                source: '節點D',
                target: '節點F'
            }, {
                source: '節點F',
                target: '節點G'
            }, {
                source: '節點G',
                target: '節點H'
            }, {
                source: '節點H',
                target: '節點I'
            }, {
                source: '節點I',
                target: '節點J'
            }, {
                source: '節點J',
                target: '節點E'
            }, {
                source: '節點E',
                target: '節點C'
            }],
            lineStyle: {
                opacity: 0.9,
                width: 2,
                curveness: 0
            }
        }
    ]
};

參考

• python實作四個數字的全排列