[Solved] CSCI 2270 Homework9 -implement graph traversal for cities

Overview

In this assignment, you will apply DF traversal for finding connected cities in a graph and find the shortest path using Dijkstras algorithm.

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:

void addVertex(string name);

• Use from the previous assignment.

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 depthFirstTraversal(string sourceVertex):

• Use Depth first traversal (recursive) from sourceVertex to traverse the graph. Print the city name and corresponding distance from the sourceVertex. Format for printing:

// for printing the path found through DF Traversal (each node) cout<< n->name << > ;

// print Done at the end when all the cities have been visited. cout << Done;

vertex* DijkstraAlgorithm(string start, string end):

• Use Dijkstras algorithm to find the shortest path in the graph from the start city to the end city.

For example: Dijkstras Shortest distance from Boulder (Bo) to Denver (De): 15

void shortestpath(string s1, string s2):

• You should print the shortest path found though the Dijkstras algorithm.

// for printing the shortest path cout << path[i]->name << ;

Other cout statements:

cout<<Depth First Traversal <<endl; cout<<endl;

cout<<Dikstras Shortest distance from Aurora to Fruita: <<vertex->distance<<endl; cout<<Dikstras Shortest path from Aurora to Fruita: <<endl;