Description

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:

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 two-dimensional array (or matrix) of integers. The meaning of a non-zero 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.