Shortest Pair

graphs

Preliminaries

The purpose of this assignment is to gain experience with Greedy and Dynamic Programming Algorithms.

If the vector library is used in this assignment, you will not receive any credit.

Lab To Do

1. Write a class called shortest that implements a directed, weighted graph using an adjacency matrix.

   To keep things simple, we will use the value 1000000 to represent infinity. You should declare it as a constant. Infinity is also represented in the math library. You can use it.

   You are going to implement Floyd2 from Chapter 3. The path algorithm on page 105 must be a private function.

   You are going to modify Dijkstra's shortest path algorithm from Chapter 4 to take a starting vertex V and calculate the shortest path from V to every other vertex.

   Your class must be in shortest.cpp and shortest.h.

   Your private section must contain the dynamically allocated 2-dimentional matrices for W, D, and P.

   You must provide the following member functions:

   • Default Constructor.

     Prompt the user for the number of vertices in the graph - n. The names of the nodes will be 1 through n, consistent with the text. Be sure to handle this properly. Dynamically allocate the 2-dimensional matrices W, P, and D. The weights and node names must be integer.

     Each entry in W must be initialized properly. The weight from nodei to nodei must be set to 0 (i.e. the diagonal). Every other entry must be set to infinity.

     Go into a loop asking the user if they have an edge to enter. The user should enter Y for yes and N for no. If the user enters N, exit the loop.

     Prompt the user first for the first node in the edge, n1, the second node in the edge, n2, and the cost of the edge. You must properly handle invalid input.

     Ensure n1 and n2 are nodes in the graph.

     Be sure to initialize all data structures stored in the private part of your class.

     Your code should print W.

   • Destructor. Clean up all of the dynamically allocated memory.
   • Dijkstra is a general member function that takes an integer parameter, V, value 1 through n that is the starting node. Dijkstra will then calculate the shortest path from V to every other node in the graph.

     You should modify Algorithm 4.3 that is presented in the text. Algorithm 4.3 assumes there is a path from the starting vertex to every other vertex. In the general, that may not be the case. You must modify the algorithm to handle that situation.

     Warning: there is a test in the code in the in Algorithm 4.3 that is semantically incorrect. If you implement that test exactly as written, your code will not work properly. Link to .out file.
     Link to .out file if you do not fix the error in the text.

     ---

     Use a linked list to represent F. At the beginning, initialize F to NULL. A node in the list:
     struct edgenode {
     int e1;
     int e2;
     edgenode * next:
     };

     The code in the text :

     e=edgefrom vertex indexed by touch[vnear] to vertex indexed by vnear;

     To implement this, create an edgenode and insert it into the beginning of F.

     At the end of the function, print F and touch.

   • Floyd2. Implement Algorithm 3.4 from your text.

     Upon completion, your code must output D. You should print each row of the matrix on a single line. It should then use the recursive path function to print the path from every vertex to every other vertex (for all i, j)

   • Write a main program to exercise your class. This should be in a file called assign2.cpp.

     The program should declare a shortest object. Then go into a loop presenting the following menu:

     1. Do Dijkstra. Prompt user for starting index.
     2. Do Floyd
     3. Exit the program.

     Your code must properly handle invalid input.

     makefile

Lab Turn In

The program is due before the start of class on the date specified on the lab page.

Last Modified 2:27 PM 6/17/2022