You will now analyze the journeys on a subway network. You are provided with a list of stations and direct routes between stations.

i) You are also provided with densities for the network where dij corresponds to the average number of people on a direct journey from station i to j (no stations other than i and j are visited during a direct journey). For convenience, we will assume that dij=dji. A safety factor, Sab, for a journey between stations a and b (not necessarily a direct journey) is defined to be the maximum density encountered during the journey (lower S corresponds to higher safety). Given a starting and destination station, develop an algorithm to efficiently find the safest journey between the two stations. Implement your method in safeJourney in part1.py. Along with the starting and destination stations, the function is provided an adjacency list, Alist, for the network. The ith element of the list is a list of tuples. Each tuple contains a station which can be directly reached from i, and the density for travel between that station and i. The function should return a list containing the sequence of stations encountered during the safest journey and the safety factor for the journey. E.g., if the function returns [[1,5,3],10] then the full journey is 1 -> 5 -> 3 and the safety factor of the journey is 10. If multiple journeys produce the same minimum S, you can return any one of those journeys.

ii) Now consider the fastest journeys between stations start and dest. You are provided with durations of journeys between stations i and j, tij (rounded to the nearest minute and tij=tji), and if there are multiple shortest journeys, you should select the one with the least number of steps. Complete shortJourney so that it efficiently finds this fastest journey and returns the stations included in the journey (as a list) and the duration of the journey. The setup of the function is very similar to safeJourney, and further details are provided in the function docstring.

def safeJourney(Alist,start,dest):

"""

i)

Find safest journey from station start to dest

Input:

Alist: List whose ith element contains list of 2-element tuples. The first element

of the tuple is a station with a direct connection to station i, and the second element is

the density for the connection.

start, dest: starting and destination stations for journey.

Output:

Slist: Two element list containing safest journey and safety factor for safest journey

"""

Slist = [[],None] #modify

return Slist

def shortJourney(Alist,start,dest):

"""

ii)

Find shortest journey from station start to dest. If multiple shortest journeys

exist, select journey which goes through the smallest number of stations.

Input:

Alist: List whose ith element contains list of 2-element tuples. The first element

of the tuple is a station with a direct connection to station i, and the second element is

the time for the connection (rounded to the nearest minute).

start, dest: starting and destination stations for journey.

Output:

Slist: Two element list containing shortest journey and duration of shortest journey

"""

Slist = [[],None] #modify

return Slist