Cleaner method for finding the shortest distance between points in a python list?
<p>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)</p>

<p>What would be the correct way to accomplish this?</p>

<p>Here is my previous algorithm:</p>

<pre><code>def bestPath(currentPoint,goalList):
    sum = 0
    bestList = []
    while len(goallist) &gt; 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
</code></pre>

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

<p>Here is what you can do:</p>

<p>First get all combinations:</p>

<pre><code>&gt;&gt;&gt; list_of_points = [(1,2) , (2,5), (6,7), (9,3)]
&gt;&gt;&gt; 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))]
</code></pre>

<p>Then create a function that give you the length of a combination:</p>

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

    return length
</code></pre>

<p>Finally a function that test every possibility:</p>

<pre><code>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 &lt; min:
            min = length
            combination_min = combination

    return combination_min
</code></pre>

<p>Then finally you can have:</p>

<pre><code>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 &lt; 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)
</code></pre>

python for-loop while-loop distance heuristics