The goal is to design and implement two heuristic algorithms to find a shortest path in a graph. You need to design algorithms, select appropriate data structures, and write the program to implement the algorithms.

Problem Description

Your program reads two input files, which are provided below at the bottom - (1)graph_input.txt. and (2)direct_distance.txt.

The first input file contains structural information about the input graph. Your program must read the graph input file and store the information in an appropriate data structure. You can use any data structure to store the input graph.

Thegraph_input.txtfile contains a textual representation of a graph. This representation of a graph is calledadjacency matrix. In the input file, the vertex names (uppercase letters) and integers are separated by one or more spaces. Lenbe the number of vertices in a graph. There aren+ 1 columns andn+ 1 rows in the input file.

graph_input.txtfile:

ABCDEFGHIJKLMNOPQRSTZ

A0710000000 15100000000000

B71075000000000000000000

C0750 11800000 14000000000000

D00 1180 1110000000000000000

E000 111070000000000000000

F00007007500000000000000

G00000750 1200000000000000

H000000 1200 14600 1380000000 1150

I0000000 146080097000000000

J 1510 14000000800990000000000

K000000000990000000000 211

L0000000 1389700000000000 101

M0000000000000000000090

N00000000000000098 14200085

O0000000000000008600000

P00000000000009886000000

Q0000000000000 14200092000

R00000000000000009208700

S0000000000000000087000

T0000000 1150000000000000

Z0000000000 211 10190850000000

The second input file, nameddirect_distance.txt, has thedirect distancefrom each node to the destination nodeZ. The direct distance from a nodento nodeZis the distance measured along animaginary straight line(or geographically straight line) from nodento nodeZand is not necessarily the same as the sum of the weights of the edges connectingntoZ.

The second input file direct_distance.txt , corresponding to the above input graph:

A 380

B 374

C 366

D 329

E 244

F 241

G 242

H 160

I 193

J 253

K 176

L 100

M 77

N 80

O 161

P 151

Q 199

R 226

S 234

T 92

Z 0

You are required to implement two heuristic algorithms that are described below. Both algorithms try to find a shortest path from a given input node to node Z using heuristic approaches. In a shortest path, a node may appear at most once (i.e., a node cannot appear twice or more in a path).

Note that these two heuristic algorithms do not always find a correct shortest path.

Both algorithms start with the given input node and iteratively determine the next node in a shortest path. In determining which node to choose as the next node, they use different heuristics.

Letw(n,v) be the weight of the edge between nodenand nodev. Letdd(v) be thedirect distancefromvto the destination node Z.

When choosing the next node from a current noden:

Algorithm 1: Among all nodesvthat are adjacent to the noden, choose the one with the smallestdd(v).

Algorithm 2: Among all nodesvthat are adjacent to the noden, choose the one for whichw(n,v) +dd(v) is the smallest.

We assume the followings:

The number of nodes in an input graph is 26 or smaller (Your program must be able to handle a graph with up to 26 nodes).

Each node is represented by a single uppercase letter.

The destination node is Z.

The destination node Z is reachable from all other nodes.

All distances (edge weights) are positive integers.

Specific Requirements

1.Implement both algorithms in one program. Your program may include multiple files.

2.Your program must prompt the user to enter the start node. Your program must check the validity of the user-entered start node and, if the input is invalid, your program must prompt the user to enter an input again.

3.Then, your program must find a shortest path from the input node to node Z using each algorithm and print the output on the screen.

4.Your output must include the following three components for each algorithm: (1) The sequence of all nodes that were initially included in a shortest path. This sequence must include any backtrackings (see the example below), (2) The final shortest path found by the algorithm, (3) Shortest path length.

Output Example:

(A)User enters node J as the start node

Algorithm 1:

Sequence of all nodes: J -> K ->Z

Shortest path: J -> K ->Z

Shortest path length: 310

Algorithm 2:

Sequence of all nodes: J -> I -> L -> Z

Path: J -> I -> L -> Z

Length: 278

(B)User enters node G as the start node

Algorithm 1:

Sequence of all nodes: G -> H -> T -> H -> L -> Z

Shortest path: G -> H -> L -> Z

Shortest path length: 359

Algorithm 2:

Sequence of all nodes: G -> H -> T -> H -> L -> Z

Shortest path: G -> H -> L -> Z

Shortest path length: 359

Note:

These two algorithm do not always find a correct shortest path.

You can use the given graph to test your program

You must also include the pseudocodes of both algorithms that you used to implement the algorithms