Project Assignment
The goal of this assignment is to give students an
opportunity to design and implement two heuristic algorithms to find a shortest
path in a graph. You need to read the problem description carefully, design algorithms,
select appropriate data structures, and write a program to implement the
algorithms.
Problem Description
Your program reads two input files – (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.
The graph_input.txt
file contains a textual representation of a graph. The following example
illustrates the input file format.
Consider the following graph. Each node has a name (an
uppercase letter in a circle) and each edge is associated with a number. The
number associated with an edge, which is called weight of the edge, represents the distance between the two
vertices that are connected by the edge. We assume that all distances are positive
integers.
The graph is represented in the input file as follows:

H 
I 
L 
M 
N 
Z 
H 
0 
146 
138 
0 
0 
0 
I 
146 
0 
97 
0 
0 
0 
L 
138 
97 
0 
0 
0 
101 
M 
0 
0 
0 
0 
0 
90 
N 
0 
0 
0 
0 
0 
85 
Z 
0 
0 
101 
90 
85 
0 
This representation of a graph is called adjacency matrix. In the input file, the
vertex names (uppercase letters) and integers are separated by one or more
spaces. Le n be the number of
vertices in a graph. There are n + 1
columns and n + 1 rows in the input
file. The top row and the first column show the names of vertices. The main
part of the input file is an n x n twodimensional array (or matrix) of
integers. The meaning of a nonzero integer at the intersection of row i and column j is that there is an edge connecting the vertex corresponding to row
i and the vertex corresponding to
column j, and the integer is the
distance between the two vertices. For example, the “138” at the intersection
of the first row and the third column in the matrix means there is an edge
between the vertex H and the vertex L and the distance is 138. The entry 0
means that there is no edge connecting two corresponding vertices. For example,
the “0” in the sixth row and the first column in the matrix means that there is
no edge between the two vertices Z
and H.
Suppose that a network of cities is represented by a
weighted, undirected graph as shown below. Each node in the graph represents a
city, the edge between two nodes represents a road connecting the two cities,
and the weight of an edge represents the distance between the two cities on the
connecting road.
The second input file, named direct_distance.txt, has the direct
distance from each node to the destination node Z. The direct distance from a node n to node Z is the
distance measured along an imaginary
straight line (or geographically straight line) from node n to node Z and is not necessarily the same as the sum of the weights of the
edges connecting n to Z.