shortest_route_algorithm.py

__author__ = 'David Gotz, [email protected], Onyen = gotz'


# A City has a name and a set of departing routes
class City:
    def __init__(self, city_name):
        self.city_name = city_name
        self.routes = []

    def add_departure(self, route):
        self.routes.append(route)

    def get_departures(self):
        return self.routes

    def get_city_name(self):
        return self.city_name


# Each route has a destination and a distance.
class Route:
    def __init__(self, destination, distance):
        self.destination = destination
        self.distance = distance

    def get_destination(self):
        return self.destination

    def get_distance(self):
        return self.distance


# Recursive function to din the shortest path.
def find_shortest_path(start_city, end_city):

    # Are we at the end city?  If so, the route is just the end city and the length is zero!
    if start_city.get_city_name() == end_city.get_city_name():
        result = (0, [start_city.get_city_name()])
    else:
        # We aren't at the end city.  So we need to look at all departures to see which is shortest.
        # Start by priming a loop with the first route's data.
        first_route = start_city.get_departures()[0]
        shortest_dist, shortest_city_list = find_shortest_path(first_route.get_destination(), end_city)
        shortest_dist += first_route.get_distance()
        shortest_city_list.insert(0, start_city.get_city_name())

        # Now loop over remaining routes to find the shortest.
        for route in start_city.get_departures()[1:]:
            # Compute the shortest path for this destination.  This is the recursive call!
            path_dist, city_list = find_shortest_path(route.get_destination(), end_city)

            # Add in this route's distance and start city.
            path_dist += route.get_distance()
            city_list.insert(0, start_city.get_city_name())

            # Is this the shortest so far? If so, save it.
            if path_dist < shortest_dist:
                shortest_dist = path_dist
                shortest_city_list = city_list

        # Once we are done with all departing routes, we just return the shortest one.
        result = (shortest_dist, shortest_city_list)

    return result


def main():
    # Create the cities.
    boston = City("Boston")
    new_york = City("New York")
    philadelphia = City("Philadelphia")
    pittsburgh = City("Pittsburgh")
    washington = City("Washington")
    richmond = City("Richmond")
    raleigh = City("Raleigh")
    knoxville = City("Knoxville")
    charlotte = City("Charlotte")
    atlanta = City("Atlanta")

    # Define the one-way routes.
    boston.add_departure(Route(pittsburgh, 18))
    boston.add_departure(Route(new_york, 9))
    new_york.add_departure(Route(pittsburgh, 11))
    new_york.add_departure(Route(philadelphia, 5))
    philadelphia.add_departure(Route(washington, 7))
    pittsburgh.add_departure(Route(knoxville,14))
    pittsburgh.add_departure(Route(charlotte, 17))
    pittsburgh.add_departure(Route(washington, 9))
    washington.add_departure(Route(richmond, 4))
    washington.add_departure(Route(knoxville, 16))
    richmond.add_departure(Route(atlanta, 19))
    richmond.add_departure(Route(raleigh, 9))
    raleigh.add_departure(Route(atlanta, 13))
    raleigh.add_departure(Route(knoxville, 12))
    knoxville.add_departure(Route(atlanta, 7))
    charlotte.add_departure(Route(atlanta, 10))

    # Find shortest path
    dist, path = find_shortest_path(boston, atlanta)
    print("Length: ", dist, " and Path:", path)

# Run the program
main()