## Description

Weighted Graphs (1 1 0 points)

Purpose

• to familiarize you with graphs

• to help you understand breadth-first search

• to aid in understanding shortest-path algorithms

• to use the Standard Template library

• you may also use the eset> library, if you wish

Tasks

• createa Graph class

• constructor

• void source, std:string target int weight)

• void AddVertex(stdrstring label)

• int label) const // -1 if label is not found

• bool lsEdge(int sourcelndex, int targetlndex) const

• int GetWeight (int sourcelndex. int targetlndex) const

• void greadthFirstSearch(string startingVertex) const

• void BreadthFirstSearch(std::string startingVertex, int visitedD const

• void DijkstraShortestPath (string startngVertex) const

• void startingVertex, inl distanced, int prevVertexJ) const

• void PrintGraph() const

• static int

• test Graph class with the provided driver (Main_cpp)

This graph is similar to the one we did in class. The major difference is that this is a •weighted’ graph. The one in class used a matrix of

bools to denote an edge. This one needs a matrix of •int•s•. If there is an edge, then the location in the matrix holds the weight value of that

edge, otherwise, the value holds the defined INT_MAX (which is just the largest number an integer can hold. If you *include eclimits>, then

INT-MAX is already defined for you)

The static const fit MAX_VERTECIES defines how large the matrix needs be. It really should be Left at a value of at least 10,

There are overloads on both DijkstraShortestPathO and BreadthFirstSearchO. The one which don’t require any additional arrays are to

simply output their results to cout The ones which do require additional arrays are used by the unit tests and will be fully described in class.

The function without the extra parameters should be able to use the other functions to do the •heavy lift’ and then display the output from

the supplied arrays.

If the output of Printo looked like this:

aumverticies: /

v;

The Nisited• array for BreadthFirstSearch(‘VO”, visited) would be

, -1, – 1 The first element is the index of the starting vertex The subsequent elements are the visited vertices in the

proper •Breadth First’ order The -1 signify an unused vertex.

If BreadthFirstSearch(“VC”) were called, the output would look like

starting BFS with vertex V3

visited

visited

visited

visited

visited

visited

vo

The ‘distance” and ‘prevVertex” arrays for DijkstraShortestPathCV3•, distance, prevVertex) would be

{5, 6, INT_MAX, O, 7, 6, 7} // distance[]

{3, O, INT_MAX, INT_MAX, C, 3, 3} // prevVertexL

If DijkstraShortestPath(V3V) were called, the output would look like

hortest Distance starting from vertex V3

to:

to:

to:

to:

to:

to:

to:

V2

1

2

no path

2

1

1

Path:

Path:

Path:

Path:

Path:

Path:

vo,

VI,

vo,

vo,