(20 points) Consider a list of n airports, and a list of m flights. The informat
ID: 3588281 • Letter: #
Question
(20 points) Consider a list of n airports, and a list of m flights. The information of the k-th flight is given to us as a quadruple (ak, bk, tk, dk), where ak is the name of the origin airport, be is the destination airport, tk is the time of departure, and dk is the time of arrival Given four parameters a, b, s, t, we want to see that starting at time s at airport a, we can take a sequence of flights to get to b no later than time t. Here we assume that transferring from one flight to the next takes no time. Give an algorithm that solves this problem in O(m +n).Explanation / Answer
dijkstra's algorithm:
mark N as known
return //exit
else
for each node A adjacent to N
if(Ns reached time +time of(N,A))<A’s time)
A’s time=N’s time+time of(N,A)
Prev[A]=N//
if( A is bk && time of(A)<=t )
mark A as known
return //exit
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.