若干个点的最短路径方式以及绘制连线图（Python）

1.输入

import matplotlib.pyplot as plt
import numpy as np
import math
from pylab import *
print("请输入方格纸的大小a b")
ab=np.array((input().split()),int)
print("请输入点的个数n：")
n=int(input())
print("请输入各个点的横坐标")
x=np.array((input().split()),int)
print("请输入各个点的纵坐标")
y=np.array((input().split()),int)

2.计算长度的函数

首先我们先写出计算两个点之间的距离，再把他们按照不同的顺序相加

def distance(x1,y1,x2,y2): #计算两点之间的距离
    d=pow((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2),0.5)
    return d
#------------------------------以下是计算长度总和
def length(a):
    i=0
    l=0
    while i 
3.找出不同的连线方式
 
在此我们的思路是先将n个点编号为0~n-1，同时我们将数组一个包含n个零的一维数组从第n-1位加一，每逢n-1则进位，如n=3时，则会产生[0,0,0],[0,0,1],[0,0,2],[0,1,0],[0,1,1],[0,1,2],[0,2,0]一直到[2,2,2]这便代表了不同的连线方式，显然其中会有不少重复的连线方式，且同一个点不能被连接两次，如[0 1 2]与[2 1 0]是完全一样的，[0,0,0] [0,0,1]这种连线方式也不应该存在，因此我们还需要删去他们
 
进位函数：
 
def carry(b,i):
    b[i]=0
    b[i-1]=b[i-1]+1
    if(b[i-1]>=n):
        carry(b,i-1)
 
检查出0123 3210这种相同的连线方式：
 
def check(a,b): #这个函数用来检查连接方式是否是一样的，如ABCD=DCBA如果一样。将二者变得一样
    ch=0
    i=0
    while i
 
生成不同连接方式并删去相同的连线方式：
 
i=0
b=np.zeros(n)
b[n-1]=-1
c=np.zeros(n)
c[n-1]=1
cc=1
ccc=0
while cc==1:
    m=0
    b=b+c     #这里便是上述中一直加一的部分
    if(b[n-1]>=n):
        carry(b,n-1)
    i1=0
    while i1 
4.筛选出最小连线方式
 
比大小找出最小的，并且记录他们在newnum中位置，即记录他们所对应的连线方式
 
length2=np.empty(int(0.5*math.factorial(n)))#length2是为了记录不同连线方式在newnum中的位置
i=0
while i 
5.连接最小连线
 
我们现在已经找出最小连线方式在newnum中的位置，并且把它储存在minlength接下来只需要连线即可
 
def connect(a):
    i=0
    #plt.figure(figsize=(4,4))
    while i
 
下面展示一下运行结果：
 
 
 
 
 
另外附上总代码
 
import matplotlib.pyplot as plt
import numpy as np
import math
from pylab import *
print("请输入方格纸的大小a b")
ab=np.array((input().split()),int)
print("请输入点的个数n：")
n=int(input())
print("请输入各个点的横坐标")
x=np.array((input().split()),int)
print("请输入各个点的纵坐标")
y=np.array((input().split()),int)
l=0
k=0
#print(x,y)
length1=np.empty(math.factorial(n))
number=np.empty([math.factorial(n),n])
#d=np.empty(0.5*n*(n-1))
#-------------------------------------------         这个函数用来绘制连线图
def connect(a):
    i=0
    #plt.figure(figsize=(4,4))
    while i=n):
        carry(b,i-1)
while cc==1:
    m=0
    b=b+c
    if(b[n-1]>=n):
        carry(b,n-1)
    i1=0
    while i1 
感谢观看！！！