#!/usr/bin/python # # This code is hereby granted to the public domain. import sys INFINITY = 9999 # close enough # city_graph is the "from" city, with connected "to" cities and their # distances (km): city_graph = { 'copenhagen': {'hannover':475, 'berlin':435}, 'hannover': {'copenhagen':475, 'berlin':290, 'frankfurt':350}, 'berlin': {'copenhagen':435, 'hannover':290, 'frankfurt':545, 'leipzig':190}, 'frankfurt': {'hannover':350, 'berlin':545, 'leipzig':395, 'stuttgart':210}, 'leipzig': {'berlin':190, 'frankfurt':395, 'stuttgart':480}, 'stuttgart': {'frankfurt':210, 'leipzig':480}, 'newyork': {'sanfrancisco':4675}, 'sanfrancisco': {'newyork':4675}, } # city_info will contain the best distance from key city to the source # city of the search, plus the parent pointer in that direction. # e.g. 'copenhagen': {'distance':INFINITY, 'parent':None}, city_info = {} #--------------------------------------------------------------------- def find_closest_city(city_list): """Find the city in the list with the shortest distance. Return None if all cities are infinitely far.""" closest = None closest_dist = INFINITY for city in city_list: dist = city_info[city]['distance'] if dist < closest_dist: closest_dist = dist closest = city return closest #--------------------------------------------------------------------- def usage(): sys.stderr.write('usage: %s cityto cityfrom\n\n' % sys.argv[0]) sys.stderr.write(' Valid cities are:\n') for city in city_graph.keys(): sys.stderr.write(' %s\n' % city) sys.exit(1) #- MAIN -------------------------------------------------------------- if len(sys.argv) != 3: usage() # get command line cities starting_city = sys.argv[1].lower() ending_city = sys.argv[2].lower() # make sure user entered a valid starting city try: city_graph.keys().index(starting_city) except: usage() # create the unvisited set unvisited_list = city_graph.keys() # create and initialize the city distance array for city in city_graph.keys(): city_info[city] = {'distance':INFINITY, 'parent':None} # distance from starting city to itself is 0: city_info[starting_city]['distance'] = 0 found = False # relax the graph: while len(unvisited_list) > 0: closest_city = find_closest_city(unvisited_list) #sys.stderr.write('closest city %s\n' % (closest_city)) # this could happen if every city in the list is infinitely far # away--it means all remaining cities are on different "islands" # than the starting city, so the destination must therefore be # unreachable: if closest_city == None: break if closest_city == ending_city: # found the goal--all done! # you could keep going until the whole graph was completed # if you wanted--but that takes time, so we just bail here: found = True break neighbor_list = city_graph[closest_city].keys() for neighbor_city in neighbor_list: closest_city_dist = city_info[closest_city]['distance'] neighbor_city_dist = city_info[neighbor_city]['distance'] #sys.stderr.write('examining %s (dist=%d) from %s (dist=%d)\n' % (neighbor_city, neighbor_city_dist, closest_city, closest_city_dist)) road_length = city_graph[closest_city][neighbor_city] new_dist = closest_city_dist + road_length if new_dist < neighbor_city_dist: # relax the neighbor city #sys.stderr.write(' relaxing %s from %s, old=%d, new=%d\n' % (neighbor_city, closest_city, neighbor_city_dist, new_dist)) city_info[neighbor_city]['distance'] = new_dist city_info[neighbor_city]['parent'] = closest_city # all done relaxing this city's neighbors, so drop it from the list # and we'll go on to the next-closest on the next iteration of the # loop: unvisited_list.remove(closest_city) # either we exhausted the entire graph, or there were no more cities on # the starting city's "island": if not found: sys.stdout.write('No route from %s to %s\n' % (starting_city, ending_city)) sys.exit(2) # now we can build a list of cities from the ending city to the starting # city just by following the parent pointers from the ending_city: route = [] cur_city = ending_city while cur_city != None: route.append(cur_city) cur_city = city_info[cur_city]['parent'] # reverse the route for presentation to the user route.reverse() # output result sys.stdout.write('Route from %s to %s (total distance %d km):\n' % \ (starting_city, ending_city, city_info[ending_city]['distance'])) for city in route: sys.stdout.write(' %s\n' % city)