Suppose that a travel agent asks you to design and develop an algorithm that computes the quickest itinerary from Alabama bus station to every other state in USA, using a train or a bus. For that the agent gives you the following information as input:

- for every state, there is at most 1 designated train station in the state

- for every state, there is at most 1 designated bus station in the state

- for every 2 states whether there is a direct train transportation

- for every 2 states whether there is a direct bus transportation

- the average travel times between 2 states by a train if direct train transportation between those 2 states is possible

- the average travel times between 2 states by a bus if direct bus transportation between those 2 states is possible

- for every state that has both a train and a bus station, the average travel time between the train and bus station

It is also given that a passenger can transfer between the bus and train stations inside the state but at most once and there is no waiting at any station between travels.

The task is to design an algorithm using dynamic programming to solve the travelling problem, provide guarantees about its correctness, termination and computational efficiency (analysis of its asymptotic time/space complexities), implementing the algorithm in Python and testing its functionality

This is what is wanted:

a) Recursive formulation of the traveling problem: Identify the subproblems, observe the optimal substructure property and the overlapping computations, and then dene the problem recursively respecting a topological ordering