Input:
You are given a directed graph G modeling a flight network: There is an edge from airport A to B if there is a direct flight from A to B. The capacity of an edge e is labeled with the corresponding flight capacity cap(e). Each edge has a start time st(e) and a finish time ft(e).
Task:
Given a source and a target airport, our goal is to find the maximum number of passengers that can be sent from the source airport starting at 6AM to the target airport within 5 hours (11AM).
Example: (e_1: A to B cap 80, st 6AM, ft 9AM), (e_2: B to C cap 100, st 7AM, ft 11AM), (e_3: B to C cap 60, st 10AM, ft 11AM). If the input contains A as the source and C as the target, then the output is 60 passengers.
Give an efficient algorithm (to the best of your knowledge) and aformal proof of correctness for your algorithm. An answer without any formal proof will be considered incomplete.Analyze the running time of the algorithm.
You must write down your algorithm as pseudocode or describe it as a set of steps (as we do in the class).Do not provide code that is written in a code editor using C/C++/Python/Java, etc.