Consider $8$ different cities $($not $$zmir and not Van$)$ in Turkey including

your hometown and your parents$$ hometowns $($If you are not from

Turkey, choose the cities you have visited or you want to visit$).$

Construct a table for distances between the $10$ cities including the $8$

cities you have chosen and $$zmir and Van using the date given the picture below which represents distances between cities. Let X be the average distance between these $10$ cities.

Discuss if the following questions can be solved using Dijkstra algorithm

or dynamic programming algorithm. If yes, then write a computer

program that implements the algorithm.

$1)$ Assume that you will be given a task where you start from $$zmir

visit some of the other $8$ cities on the way and reach to Van,

where you stay exactly one night in an intermediate city, move to

another one next morning and reach there in the same evening.

You may come back to the same intermediate city. What is the

minimum distance you must travel for such a task $($including at

least one night$-$stay$)?$ What is the minimum distance if the task

contains exactly $4$ nights$-$stay.

$2)$ Assume that for the above task you spend $1$ TL per km and earn X

TL for each city you visit. Which tasks are the best and worst in

terms of total income?

In Task $1,$ there are two subtasks:

The first one is to find the minimum distance from $$zmir to Van if you visit at least one intermediate city.

The second one is to find the minimum distance from $$zmir to Van if you visit exactly four intermediate cities.

The number of night stays $=$ The number of intermediate cities $($you stay one night at an intermediate city$)$

In Task $2,$ you should analyse Task $2$ with a change in the cost function.

If you do not know how to write a computer program, you can reduce the total number of cities from $10$ to $5$ and apply the algorithm on paper. IF you choose to do it by hand and therefore use $5$ cities then you should change th $4$ nights stay condition to $2-$nights stay.