Question
Complete the function to find a path between two vertices of the graph minimizing the weight of the maximum-weight edge in the path using the
Complete the function to find a path between two vertices of the graph minimizing the weight of the maximum-weight edge in the path using the priority queue ((|E|+|V|)log|V|) implementation of the Dijkstras algorithm in python.
Along with the two vertices-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 mini-maximum weight of the edges along the journey is 10. If multiple journeys produce the same minimum, you can return any one of those journeys.
(So for example, in the picture above, the safe factor from 1 to 3 is 3 and safeJournet(Alist,1,3) should return [[1,2,3],3]. )
def safeJourney(Alist,start,dest):
"""
Find the 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
the safe factor is the smallest maximum weight among all possible paths from starting to destination stations
"""
Slist = [[],None] #modify
return Slist
target source widest path: 1-4-3 widest_distance: 2 target source widest path: 1-4-3 widest_distance: 2Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started