Write the following code: the journeys on a subway network. A list of stations and direct routes between stations will be provided.

i) You are also provided with densities for the network where d_ijcorresponds 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 d_ij = d_ji. A safety factor, S_ab, 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 provided below. Along with the starting and destination stations, the function is provided with 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.

def safeJourney(Alist,start,dest):

# """

# 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

Briefly discuss the running time and efficiency of your implementation

Note: You are not allowed to use heapq, however, if you determine that the best approach to a problem requires a binary heap, you should choose this approach, implement it without a heap, and then discuss the benefits of the heap (and its influence on the asymptotic running time) in your analysis.