I. THE PROBLEM

A salesmen needs to travel from city A to city D (represented by vertices A and D, respectively, in the graph below). The salesman is facing the following  problems:

[Problem 1] How many trip options are available, if only the cities along the path need to be considered? (e.g., the possible trip options would be 2 if there are a path A-­ B-­‐D and a path A-­‐C-­‐D, regardless the cost for each path).

[Problem 2] How many trip options are available, if only the total monetary cost needs to be considered? What are the two least expensive trip options? What are the cities along each identified path and the monetary cost for travelling between these  cities.

[Problem 3]  ow many trip options are available, if  only the total travel time needs to be considered? What are the two least-­‐time trip options? What are the cities along the path and the time-­‐cost for travelling between these cities?

[Problem 4] How many trip options are available, if the salesman needs to reach city D in 3 days with a budget of $1000? What are the best  two options you would recommend to him? What are the cities along the path and the associated costs for travelling between these cities? What is the rationale that these two options are selected as the best two options?

 

Attached is the graph for the problems stated above.

I need help to develop algorithms to solve those four problems given above.

Thanks.

 

Attachments:

• 1495179112-assigment 2.png