Weighted Graphs Solution



to familiarize you with graphs

to help you understand breadth-first search

to aid in understanding shortest-path algorithms to use the Standard Template <queue> library you may also use the <set> library, if you wish


create a Graph class constructor

void AddEdge(std::string source, std::string target, int weight}

void AddVertex( std string label}

int Getlndex(std::string label} const; II -1 if label is not found boollsEdge(int sourcelndex, int targetlndex) const

int GetWeight (int sourcelndex, int targetlndex) const void BreadthFirstSearch(string startingVertex} const

void BreadthFirstSearch(std::string startingVertex, int visitedO} const void DijkstraShortestPath (string startingVertex) const

void DijkstraShortestPath(std::string startingVertex, int distancel] int prevVertexO) const;

void PrintGraphO const

static const int MA)(_ VERTECIES = 10; –

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 bool’s 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 <climits>, then INLMAX is already defined for you.)

The static const int 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:

numVprtiriP’: I

va VI V2 V3 V4

va 1 2

Vi 3


2 4

V3 ‘>



The “visited’ array for BreadthFirstSearch(“VO”, visited) would be

{O, 0, 1, 4, 3,5,6, -1, -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 ‘s signify an unused vertex.

If BreadthFirstSearch(‘VO”) were called, the output would look like

starting BFS with visited vertex

V3 V3


visited V0



visited visited V6


The “distance” and “prevVertex” arrays for OijkstraShortestPath(‘V3’, distance, prevVertex) would be

{5, 6,INT _MAX, 0, 7, 6, 7} II distancel]

{3, 0, INT_MAX, INT_MAX, 0, 3, 3} 1/ prevVertexO

If DijkstraShortestPath(“V3′) were called, the output would look like

hortest Distance starting from vertex V3