Connect all cities.

Share

Home>ICT>Python by ...>Connect al...

Find the shortest route to connect all the cities.

1
# Author: HUANG KWUN HOI (SKHBBSS, class 4D)
2
# Last modified: 2020.9.27
3
draw=True
4
import math
5
import tkinter as tk
6
filename=input('Enter the data file name:')
7
print('Hold down #Enter for some time')
8
f=open(filename,'r')
9
tk.TkVersion
10
top=tk.Tk()
11
top.title('Route')
12
C=tk.Canvas(top,bg='white',width=1820,height=920)
13
xy_list=[]
14
station=[]
15
def cal(x1,x2,y1,y2):
16
    x_diff=float(x1-x2)
17
    y_diff=float(y1-y2)
18
    result=abs(math.sqrt(x_diff**2+y_diff**2))
19
    return result
20
for data in f:
21
    a=data
22
    b=a.split(',')
23
    xy_list.append([int(b[1]),int(b[2])])
24
f.close()
25
qq=len(xy_list)
26
station.clear()
27
station.append(xy_list[0])
28
shortest_distance=0
29
for q in range(qq-1):
30
    shortest=999999
31
    for w in station:
32
        for e in xy_list:
33
            ww=cal(e[0],w[0],e[1],w[1])
34
            if e not in station and ww<shortest:
35
                shortest=ww
36
                ee=w
37
                rr=e
38
    station.append(rr)
39
    shortest_distance+=cal(ee[0],rr[0],ee[1],rr[1])
40
    if draw:
41
        C.create_line(ee[0],ee[1],rr[0],rr[1])
42
    C.pack()
43
    pause=input()
44
print('Total length: ',shortest_distance)
45
top.mainloop()
 

Download source code

Download data file