Description
Weighted Graphs
cs2420 (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,
