Quinty - 2 months ago 10
Python Question

# Cleaner method for finding the shortest distance between points in a python list?

I have a list of tuples and an individual point in python e.g. [(1,2) , (2,5), (6,7), (9,3)] and (2,1) , and I want to figure out the fastest path possible created by all combinations of the individual point to the list of points.(Basically I want to find the most efficient way to get to all of the points starting from (2,1)). I have a manhattanDistance function that can take it 2 points and output the distance. However, my algorithm is giving me inconsistent answers (The heuristic is off for some reason)

What would be the correct way to accomplish this?

Here is my previous algorithm:

``````def bestPath(currentPoint,goalList):
sum = 0
bestList = []
while len(goallist) > 0:
for point in list:
bestList.append((manhattanD(point,currentPoint),point))
bestTup = min(bestList)
bestList = []
dist = bestTup[0]
newP = bestTup[1]
currentPoint = newP
sum += dist
return sum
``````

Since you don't have so many point, you can easily use a solution that try every possibility.

Here is what you can do:

First get all combinations:

``````>>> list_of_points = [(1,2) , (2,5), (6,7), (9,3)]
>>> list(itertools.permutations(list_of_points))
[((1, 2), (2, 5), (6, 7), (9, 3)),
((1, 2), (2, 5), (9, 3), (6, 7)),
((1, 2), (6, 7), (2, 5), (9, 3)),
((1, 2), (6, 7), (9, 3), (2, 5)),
((1, 2), (9, 3), (2, 5), (6, 7)),
((1, 2), (9, 3), (6, 7), (2, 5)),
((2, 5), (1, 2), (6, 7), (9, 3)),
((2, 5), (1, 2), (9, 3), (6, 7)),
((2, 5), (6, 7), (1, 2), (9, 3)),
((2, 5), (6, 7), (9, 3), (1, 2)),
((2, 5), (9, 3), (1, 2), (6, 7)),
((2, 5), (9, 3), (6, 7), (1, 2)),
((6, 7), (1, 2), (2, 5), (9, 3)),
((6, 7), (1, 2), (9, 3), (2, 5)),
((6, 7), (2, 5), (1, 2), (9, 3)),
((6, 7), (2, 5), (9, 3), (1, 2)),
((6, 7), (9, 3), (1, 2), (2, 5)),
((6, 7), (9, 3), (2, 5), (1, 2)),
((9, 3), (1, 2), (2, 5), (6, 7)),
((9, 3), (1, 2), (6, 7), (2, 5)),
((9, 3), (2, 5), (1, 2), (6, 7)),
((9, 3), (2, 5), (6, 7), (1, 2)),
((9, 3), (6, 7), (1, 2), (2, 5)),
((9, 3), (6, 7), (2, 5), (1, 2))]
``````

Then create a function that give you the length of a combination:

``````def combination_length(start_point, combination):
lenght = 0
previous = start_point
for elem in combination:
lenght += manhattanDistance(previous, elem)

return length
``````

Finally a function that test every possibility:

``````def get_shortest_path(start_point, list_of_point):
min = sys.maxint
combination_min = None
list_of_combinations = list(itertools.permutations(list_of_points))
for combination in list_of_combination:
length = combination_length(start_point, combination)
if length < min:
min = length
combination_min = combination

return combination_min
``````

Then finally you can have:

``````import sys, itertools

def combination_length(start_point, combination):
lenght = 0
previous = start_point
for elem in combination:
lenght += manhattanDistance(previous, elem)

return length

def get_shortest_path(start_point, list_of_point):
min = sys.maxint
combination_min = None
list_of_combinations = list(itertools.permutations(list_of_points))
for combination in list_of_combination:
length = combination_length(start_point, combination)
if length < min:
min = length
combination_min = combination

return combination_min

list_of_points = [(1,2) , (2,5), (6,7), (9,3)]
print get_shortest_path((2,1), list_of_points)
``````