from macslib import *
from itertools import permutations
# add the points as variables here
A = (2,6)
# make sure you add all the points to the points dictionary
# use a string label for each as the key, and the variable as the value
points = {'A':A}
# you might want to give your graph a title:
# edit the next line to add a title of your choice
drawTSPPoints(points)
# put your guess at the shortest route in pathGuess
# list the points in the order they should be visited
pathGuess = [A]
drawTSPPath(pathGuess, 'guess')
# brute force algorithm to calculate the shortest path
# this algorithm runs in factorial time
# don't use more than a few points or it will never complete!
possiblePaths = list(permutations(points.values()))
shortestLength = -1
shortestPath = []
for path in possiblePaths:
pathLength = 0
for i in range(len(path)):
x1 = path[i][0]
y1 = path[i][1]
x2 = path[(i+1) % len(path)][0]
y2 = path[(i+1) % len(path)][1]
pathLength += sqrt((x1-x2)**2 + (y1-y2)**2)
if shortestLength == -1 or pathLength < shortestLength:
shortestLength = pathLength
shortestPath = path
# uncomment next line to display the shortest path
#drawTSPPath(shortestPath, 'shortest', 'b--')