shortest path tsp algorithm

You could try to reduce the amount of paths to be checked by tracking the current house and all the houses visited so far. Let's say you have paths [1, 2, 3, 4] and [1, 3, 2, 4] you can check which one is shorter and only continue with it. Here's a example with the data that you provided, it's storing the distances in 2D array instead of dict but the principle is the same:

dist = [
    [0, 74, 4109, 3047, 2266], 
    [74, 0, 4069, 2999, 2213],
    [4109, 4069, 0, 1172, 1972], 
    [3047, 2999, 1172, 0, 816], 
    [2266, 2213, 1972, 816, 0]
]

# Helper function to calculate path length
def path_len(path):
    return sum(dist[i][j] for i, j in zip(path, path[1:]))

# Set of all nodes to visit
to_visit = set(xrange(len(dist)))

# Current state {(node, visited_nodes): shortest_path}
state = {(i, frozenset([0, i])): [0, i] for i in xrange(1, len(dist[0]))}

for _ in xrange(len(dist) - 2):
    next_state = {}
    for position, path in state.iteritems():
        current_node, visited = position

        # Check all nodes that haven't been visited so far
        for node in to_visit - visited:
            new_path = path + [node]
            new_pos = (node, frozenset(new_path))

            # Update if (current node, visited) is not in next state or we found shorter path
            if new_pos not in next_state or path_len(new_path) < path_len(next_state[new_pos]):
                next_state[new_pos] = new_path

    state = next_state

# Find the shortest path from possible candidates
shortest = min((path + [0] for path in state.itervalues()), key=path_len)
print 'path: {0}, length: {1}'.format(shortest, path_len(shortest))

It will output one of the shortest paths and the total distance:

path: [0, 2, 3, 4, 1, 0], length: 8384

Note that with data you provided there are two possible solutions which have equal length: [0, 2, 3, 4, 1, 0] and [0, 1, 4, 3, 2, 0].