as part of Analysis of Algorithms assignment Fun with Graph Algorithms my professor gave below questions

$1.$ Cameron Miskell and Abu Kaisar Mohammad Masum are

operating two independent courier services in the lovely Metropolitan area of Melbourne,

which also includes Palm Bay, Titusville, and Viera. Over time they have found that their

customers have become scattered throughout the city, and are complaining about longer

delivery times to deliver their packages. Cameron and Abu Kaiser therefore decide that the

best thing to do is not to compete with each other, but to form a cartel. They have shared

their customer information with each other, and would like to split the entire set of customers

into two. There are n total customers, and ti$,$j is the time it takes to travel from customer

i to j$.$ You may assume that this matrix is complete, and there is a time of travel between

every pair of customers. Cameron and Abu Kaiser would like to split the customers into

two disjoint sets A and B $($so every customer is in either set A or B$,$ but not both$)$ such

that the longest time l to travel between any pair of customers within their respective sets is

minimized. Please design an algorithm to compute l and the two sets of customers A and B

given the ti$,$j $$s $($between all customers i and j$)$ as input.

$2.$ Avoiding Airports $(3$ points$)$: Sam Arkle loves traveling and is looking to book his travel

around the world. Specifically, there are n countries that he can visit and is traveling from

country $1$ to country n$.$ There are also m flights available, where each flight i is characterized

by a four tuple $($ai

$,$ bi

$,$ si

$,$ ei$),$ where ai

is the country of departure, bi

is the country of arrival,

si

is the departure time and ei

is the arrival time. Sam can even visit all the airports en$-$route

to his destination and doesn$$t care about the total time of his journey, however he hates

waiting at airports. If he waits t seconds in an airport, he gains t

$2$ units of frustration. Help

$1$

him find an itinerary that minimizes the sum of frustration.

$3.$ Trip App $(4$ points$)$: Vidhi Patel is building a new mobile application called Trip App,

which allows users to see what$$s on their route. It models a highway as a straight line, and

points of interest as points along that line. All points have an integer coordinate as well as

a unique integral weight. The app provides a viewport, which can scale in and out. Also, to

prevent the display from becoming too cluttered, only a small number of the points with the

highest weights are shown. The initial viewport is centered at $0\mathrm{.}0,$ and shows from $1\mathrm{.}0$ to

$1\mathrm{.}0$ on the line.

There are three valid operations for changing your viewport:

$$ Zoom out: double the dimensions of your viewport while keeping the center the same.

$$ Zoom in: halve the dimensions of your viewport while keeping the center the same.

$$ Recenter: change the center of your viewport to be equal to a point of interest visible in

your viewport $($including the boundary$).$

There is an important caveat: The Trip App will not render all points of interest in a given

viewport; instead, it will only render at most three points in the viewport with the highest

weights. The remaining points with lower weights are not visible, and therefore are not valid

targets for the recenter operation.

For each point of interest, determine the minimum number of operations needed to go from

the starting viewport to a viewport where that point of interest is centered and visible.

Consider each point of interest independently. Note that you are given an array of two tuples

$($x$1,$ w$1),...,($xn$,$ wn$)$ as input, where xi

is the location of the i

th point of interest, and wi

is

its weight.

$4.$ Counting Shortest Paths $(5$ points$)$: Consider a single$-$source shortest path problem

with non$-$negative edge costs, and suppose we have already computed the shortest path cost

c$[$i$]$ from the source to every node i$.$ Show how to count the number of different s $$ i shortest

paths to every node i in linear time. Since this problem might involve numbers that are too

large to store in a single $\backslash$Theta $($log n$)-$bit word $($the usual assumption with the RAM model$),$

please assume for simplicity either that we have a RAM with unbounded word size, or that

we are using the real RAM model.

Need all solutions in Graphs algorithms only. And time complexity analysis is also required. Explaination should be specific, expert given solutions are brief.

give me the solutions for above questions from below algorithms

BFS$,$ Directed acyclic graphs using DP$,$ Dijkstra's, Bellman$-$Ford Algorithm, JOhnson's algorithm, The floyd$-$ warshall algorithm,