"""
    Author: Simon Westphahl <westphahl@gmail.com>
    Description: Brute-force implementation for solving the
    travelling salesman problem.
"""

routes = []


def find_paths(node, cities, path, distance):
    # Add way point
    path.append(node)

    # If path contains all cities, add path from
    # last to first city and return.
    if len(cities) == len(path):
        global routes
        path.append(path[0])
        distance += cities[path[-2]][path[0]]
        print path, distance
        routes.append([distance, path])
        return

    # Calculate path length from current to last node
    if len(path) > 1:
        distance += cities[path[-2]][node]

    # Fork paths for all cities not yet used
    for city in cities:
        if city not in path:
            find_paths(city, dict(cities), list(path), distance)


if __name__ == '__main__':
    cities = {
        'RV': {
            'UL': 36,
            'A': 125,
            'MM': 67
        },
        'UL': {
            'RV': 36,
            'A': 35,
            'MM': 50
        },
        'A': {
            'RV': 125,
            'UL': 35,
            'MM': 65
        },
        'MM': {
            'RV': 67,
            'UL': 50,
            'A': 65
        },
    }

    print "Start: RAVENSBURG"
    find_paths('RV', cities, [], 0)
    print "\n"
    routes.sort()
    print "Shortest route: %s" % routes[0]