Design and Analysis of Algorithms $($COM$336)$

Second Semester $2023/2024$

Project # $1$

Optimal Strategy for Minimum cost from city$1$ to city$1$ using Dynamic Programming

Write a program that solve minimum cost for traveling from city $1$ to city $2$ Problem using Dynamic Programming technique.

Problem definition:

Travelling from home in city$1$ to a hotel in city$2.$

N stopovers on the way

a$.$ a number of choices of towns for each stop,

b$.$ a number of hotels to choose from in each city.

Each trip has a different distance resulting in a different cost $($petrol$).$

Hotels have different costs.

The goal is to select a route to and a hotel in city $2$ so that the overall cost of the trip is minimized.

Your program should print out the following:

Read the input data from a file

File format:

Number of cities

Start city, end city

List of adjacent cities

Example:

Petrol cost

Hotel cost

$14$

Start, End

Start, $A,22,70$

$B,8,80$

$C,12,80$

$A,[D,8,50],[E,10,70]$

$B,[D,25,50],[E,10,70]$

$C,[D,13,50],[E,13,70]$