Computational Exercise 1: Shortest-Path Algorithms¶
Answer either all questions in the problem solving track or all questions in the programming track below.
For the two problems below, consider the following city layout. The edges (roads) are labeled with the time it takes to traverse them (in minutes).
In [2]:
import iimp6010
city = iimp6010.load_city()
iimp6010.visualize_city(city)

Problem 1¶
Luca, John, and Jack walk to school every day. Luca starts from his home in building A, John from B, and Jack from C. The school is located in building D.
Problem solving track:¶
Question A¶
You are asked to run Dijkstra’s algorithm to compute the path taken by each of the boys to the school. For each boy, list all the nodes that need to be relaxed (in execution order) as well as the optimal path taken.
Question B¶
If Luca leaves home at 8:30am, when do John and Jack need to leave their respective homes so that they arrive in school at the same time as Luca?
write your answer here
Question C¶
You are asked to use Dijkstra’s algorithm to determine which boy has the shortest commute to school. Describe how you would do it efficiently, and list all the nodes that need to be relaxed (in execution order).
Hint: There is an efficient solution that does not require running Dijkstra’s algorithm independently for each boy.
write your answer here
Programming track:¶
Question A¶
Complete the function below. It takes an input city graph that includes nodes labeled A, B, C, D, and outputs the home building of the boy who has the shortest commute to school (i.e., outputs A, B, or C).
Hint: There is an efficient solution that does not require running Dijkstra’s algorithm independently for each boy. You may use networkx’s shortest paths functions in the solution or implement your own version.
In [48]:
import iimp6010
import networkx as nx
city = iimp6010.load_city()
paths = nx.all_simple_paths(city.graph,’A’,’D’,cutoff=10)
PA=nx.shortest_path(city.graph,source=’A’,target=’D’)
print(PA)
paths = nx.all_simple_paths(city.graph,’B’,’D’,cutoff=10)
PB=nx.shortest_path(city.graph,source=’B’,target=’D’)
print(PB)
paths = nx.all_simple_paths(city.graph,’C’,’D’,cutoff=10)
PC=nx.shortest_path(city.graph,source=’C’,target=’D’)
print(PC)
random_path = []
random_path.append(PA)
random_path.append(PB)
random_path.append(PC)
print(random_path)
[‘A’, ‘n21’, ‘n31’, ‘n41’, ‘B’, ‘n51’, ‘n61’, ‘D’]
[‘B’, ‘n51’, ‘n61’, ‘D’]
[‘C’, ‘n54’, ‘n53’, ‘n63’, ‘n62’, ‘n61’, ‘D’]
[[‘A’, ‘n21’, ‘n31’, ‘n41’, ‘B’, ‘n51’, ‘n61’, ‘D’], [‘B’, ‘n51’, ‘n61’, ‘D’], [‘C’, ‘n54’, ‘n53’, ‘n63’, ‘n62’, ‘n61’, ‘D’]]
In [77]:
iimp6010.visualize_path_in_city(city,random_path[0])
weight = iimp6010.weight_sum_calc(city, random_path[0])
print(“Weight sum is: “, weight)
—————————————————————————
TypeError Traceback (most recent call last)
—-> 1 iimp6010.visualize_path_in_city(city,random_path[0])
2
3 weight = iimp6010.weight_sum_calc(city, random_path[0])
4 print(“Weight sum is: “, weight)
~/exercise1/iimp6010.py in visualize_path_in_city(city, path)
186 draw_city_on_axes(city, ax)
187 shortest_path_list = []
–> 188 for i in range(len(path) – 1):
189 shortest_path_list.append([path[i], path[i + 1]])
190 nx.draw_networkx_edges(city.graph, pos=city.node_positions, edgelist=shortest_path_list, edge_color=’r’, ax=ax, width=5)
TypeError: object of type ‘int’ has no len()

In [3]:
def calc_closest_boy():
paths = nx.all_simple_paths(city.graph, ‘A’,’D’,cutoff=10)
print(path)
random_path = []
for path in paths:
print(path)
random_path.append(path)
# write your code here!
return ‘A or B or C’
print(‘%s has the shortest commute to school’ % calc_closest_boy())
weight = iimp6010.weight_sum_calc(city, random_path[0])
print(“Weight sum is: “, weight)
File “
return ‘A or B or C’
^
SyntaxError: ‘return’ outside function
Problem 2¶
The Transportation Department has determined that a large number of commuters need to take buses from the metro station E to the office building F. They have decided to construct a road between nodes n55 and n57 having a weight of 3.
Problem Solving Track:¶
Question A¶
By adding such a road, would the commute time between the metro station and the office building be reduced? If so, how much time would be saved?
write your answer here
Question B¶
You are now asked to use Dijkstra’s algorithm to compute the optimal path from the metro station to the office that passes through a city corner n76, where you need to briefly meet your friend. Describe how would you use Dijkstra’s algorithm to compute such a path, and list all the nodes that would be relaxed (in execution order).
Note: Assume that the new n55-n57 road has been constructed and can be used.
Hint: You may use Dijkstra’s algorithm multiple times to solve this problem.
write your answer here
Question C¶
Suppose you can build a high-speed rail to connect any two nodes within the same row in the map (e.g., n17 to n67) having a travel time of 1 minute. Which two nodes would you connect so as to minimize the total travel time from Luca’s home to the metro station?
write your answer here
Programming Track:¶
Question A¶
Given an arbitrary input city graph that includes nodes labeled E, F, n55, and n57, complete the following function to determine what is the highest possible edge cost for the soon-to-be-constructed n55-n57 road such that the optimal path from E to F must still go through n55-n57. Your solution must make calls to the function shortest_path() as needed and is not allowed to alter the city graph.
You may assume that:
a. The input graph does not currently have an edge between n55 and n57 since the road hasn’t been constructed yet.
b. If an edge between n55 and n57 with a weight of 1 were to be added, the shortest path between E and F would go through it.
In [79]:
# before adding the edge
import iimp6010
import networkx as nx
city = iimp6010.load_city()
path = nx.dijkstra_path(city.graph,’E’,’F’)
iimp6010.visualize_path_in_city(city,path)

In [ ]:
import iimp6010
import networkx as nx
city = iimp6010.load_city()
def calc_highest_cost():
# write your code here!
return 1
answer = calc_highest_cost()
print(‘Your answer is %d’ % answer)
In [ ]:
# test your answer here
# If your answer is correct, the path should be different than the one above.
# It should go throught n55-n57.
# If you add 2 to your answer, result will be the same as shown above.
answer = calc_highest_cost()
print(‘Your answer is %d’ % answer)
city.graph.add_edge(‘n55′,’n57′,weight=answer)
path = nx.dijkstra_path(city.graph,’E’,’F’)
iimp6010.visualize_path_in_city(city,path)