[Solved] CSCI2270 Homework 5-Graph

In this assignment, you will implement Dijkstras algorithm to find the shortest path between cities.

Graph Class

Your code should implement graph traversal for cities. A header file that lays out this graph can be found in Graph.hpp on Moodle. As usual, do not modify the header file. You may implement helper functions in your .cpp file if you want as long as you dont add those functions to the Graph class.

Your graph will utilize the following struct:

Tuesday,

NOTE (1): Coderunner will set v->visited = false; v->distance = 0; v->pred = nullptr; for all vertices v before calling the dijkstraTraverse methods.

NOTE (2): In order to avoid issues with Coderunner for valid traversal sequences, process adjacent nodes in the order that they appear in the adjacency list, i.e., process nodes by going through the adjacency list per node from index 0 to the size of the adjacency list.

We have implemented the following methods for you:

void addVertex(string name);

• Add new vertex name to the graph.

void displayEdges();

• Display all the edges in the graph.

Format for printing:

If we create a graph with the following structure

graph.addVertex(Boulder); graph.addVertex(Denver); graph.addVertex(Las Vegas);

graph.addEdge(Boulder, Denver); graph.addEdge(Las Vegas, Denver);

We print the edges in the following manner.

Boulder > Denver

Denver > Boulder Las Vegas Las Vegas > Denver

The order of vertices printed is the same as the order in which they were added to the graph. Similarly, the order of vertices to the right of > sign is the same as the order in which the corresponding edge was added to the graph.

void addEdge(string v1, string v2, int num);

Make a connection between v1 and v2 (same as last assignment). Important point here is to add weights to the edges. Each edge will have a corresponding weight attached to it. e.g. addEdge(Aurora, Bloomington, 5);

void _grader_setAllVerticesUnvisited();

Tuesday,

void _grader_print_shortest_distance(string destination);

vertex* searchVertex(string start, vector<vertex*> &vertices)

You will need to implement the following method: void dijkstraTraverse(string start);

Use Dijkstras algorithm to compute the single source shortest path in the graph from the start city to all other nodes in its component.

• You must use searchVertex() from the source, which has been provided to you within

Graph.cpp.

• NOTE: You need to update the distance and pred attributes for each v.

NOTE 1: Do not modify any code provided to you other than dijkstraTraverse(). So, do not change any of the code within Graph.cpp or Graph.hpp.

NOTE 2: Once you are done with your assignment in Coderunner, you need to click on Finish attempt and the Submit all and finish. If you dont do this, your solution will not be graded.

Example Run: For the given the following Graph and the corresponding adjacency list