DESCRIPTION

Write a program that will display the minimum path between any two vertices in a given graph. The program will input the graph from a file provided by the user. It will prompt the user for entering the name of the start vertex and the end vertex. It will find the minimum path between the two vertices. It will display the minimum path showing all the vertices along the path. It will also display the total distance along the minimum path.

TESTING

Test the program for two data sets included in this module as text files. For each data set, carry out a number of test runs as listed below.

Data Set 1

Test the program for the data set 1 listed. Enter this data into a file and input the data from the file.

The data consists of two parts. In the first part, each line represents a vertex. It contain two values. The first value specifies the vertex number. The second value specifies the vertex name. The first part ends when a line contains -1 by itself. In the second part, each line represents an edge. It contains three values. The first two values specify two vertices connecting the edge. The third value specifies the weight of the edge. This part ends when a line contains -1 by itself.

0 SF

1 LA

2CHICAGO

3 NY

4PARIS

5LONDON

-1

0 1 80

0 2 200

0 3 300

1 2 230

1 5 700

2 3 180

3 4 630

3 5 500

4 5 140

-1

Data Set 1: Test Run 1

Run the program using SF as the start vertex. Program input/output dialog is shown below. The user input is shown in bold.

Enter Start Vertex:SF

Enter End Vertex :LONDON

Min Path: SF LALONDON780

Data Set 1: Test Run 2

Enter Start Vertex:SF

Enter End Vertex :PARIS

Min Path: SF LALONDONPARIS920

Data Set 2:

Data set 2 is available in a file attached.

For data set 2, run the program several times: each time use the same vertex (the first vertex input) as the start vertex and a different vertex as the destination vertex till each vertex has been used as the destination vertex.

IMPLEMENTATION

MinPath algorithm finds the minimum path from a specified start vertex to a specified target (destination) vertex in a graph and displays the following.

The list of all the vertices in the minimum path from the start vertex to the target vertex.

The total distance from the start vertex to the target vertex along the above path.

Methodology

MinPath algorithm accomplishes the above by using a variation of BreadthFirst traversal algorithm covered in a previous assignment with the following additional provisions.

It uses a priority queue (PmainQ) instead of a regular queue.

In the queue, it enqueues a vertex as an item describing the vertex.The vertex item contains the following fields:

• Total Accumulated Distance: The total distance from the start vertex to this vertex.
• Path List: The list of all vertices in the path from the start vertex to this vertex.The list of vertices is stored as an array of ints (vertex numbers).
• Path Length: The length of the above array.

In the priority queue (PmainQ), the vertex items are enqueued in ascending order of the Total Accumulated Distance values in the item vertices.

The item vertices are enqueued and dequeued form the PmainQ using a procedure similar to the BreadthFirst algorithm and is presented below.

You may use the code below as a guidance - but I strongly encourage you to design your own algorithm

1. Enqueue the start vertex item in the priority queue: PmainQ.
2. Repeatedly: dequeue a vertex item and enqueue its adjacent vertex items as below

until the target vertex is found or the PmainQ becomes empty.

Dequeue a vertex item.

If (the dequeued vertex item is the target vertex item or PmainQ is empty)

go to step 3

Else

If it is not previously Marked Visited

Mark it "visited".

Get a list of all its adjacent vertices.

Enqueue all adjacent vertices that are not previously marked visited into the PMainQ.

Algorithm

 //The above methodology is presented below as an algorithm. Enque the start vertex item in the PmainQ. While ( !( PmainQ.isEmpty() ) ) { Deque a vertex item from the PmainQ. //Process the vertex item dequeued as follows. If( vertex is unmarked ) { If ( vertex is the target vertex ) break from the loop; Mark the vertex as visited. //Get a list of all its adjacent vertices by calling a method (say getAdjacent ) as below. //(Note: getAdjacent returns adjacent vertices in a queue, adjacentQ, passed to it as below). //(Note: getAdjacent returns vertices in order with the lowest numbered vertex first). getAdjacent (vertex, adjacentQ) //Process the adjacent vertices by dequeing them from the adjacent queue //and enqueueing them in PmainQ as below. While ( !( adjacentQ.isEmpty() ) ) { Dequeue a vertex from adjacentQ. If( adjacent vertex is unmarked ) { Enqueue the adjacent vertex item in the PmainQ. } } } }

If the target vertex item is found,

Display the item contents including:

The total distance from the start vertex to the target vertex.

The list of all vertices along the above path.

Else

Display message: "Vertex Not Found".