Programming Project 5 Dijkstra's Algorithm Solution

Instructions

For Programming Project 5, you will be implementing a undirected weighted Graph ADT and performing Dijkstra's Algorithm to find the shortest path between two vertices. Your graph can be implemented using either an adjacency list, adjacency matrix, or an incidence matrix. Your graph will implement methods that add and remove vertices, add and remove edges, and calculate the shortest path. Each vertex in your graph will have a string label that will help identify that vertex to you and the test file.

A large portion of this assignment is researching and implementing Dijkstra's Algorithm. There is information about this algorithm in your textbook and widely available on the web.

Abstract Class Methods

void addVertex(std::string label)

Creates and adds a vertex to the graph with label. No two vertices should have the same label.

void removeVertex(std::string label)

Removes the vertex with label from the graph. Also removes the edges between that vertex and the other vertices of the graph.

void addEdge(std::string label1, std::string label2, unsigned long weight)
Adds an edge of value weight to the graph between the vertex with label1 and the vertex with label2. A vertex with label1 and a vertex with label2 must both exist, there must not already be an edge between those vertices, and a vertex cannot have an edge to itself.

void removeEdge(std::string label1, std::string label2)

Removes the edge from the graph between the vertex with label1 and the vertex with label2. A vertex with label1 and a vertex with label2 must both exist and there must be an edge between those vertices

unsigned long shortestPath(std::string startLabel, std::string endLabel, std::vector<std::string> &path)
Calculates the shortest path between the vertex with startLabel and the vertex with endLabel using Dijkstra's Algorithm. A vector is passed into the method that stores the shortest path between the vertices. The return value is the sum of the edges between the start and end vertices on the shortest path.
Examples

Below in an example of the functionality of the implemented graph:

std::vector<std::string> vertices1 = { "1", "2", "3", "4", "5", "6" }; std::vector<std::tuple<std::string, std::string, unsigned long>> edges1 = { {"1", "2", 7}, {"1", "3", 9}, {"1", "6", 14}, {"2", "3", 10}, {"2", "4", 15}, {"3", "4", 11}, {"3", "6", 2}, {"4", "5", 6}, {"5", "6", 9} };

for (const auto label : vertices1) g.addVertex(label);

for (const auto &tuple : edges1) g.addEdge(std::get<0>(tuple), std::get<1>(tuple), std::get<2>(tuple));

g.shortestPath("1", "5", path); // == 20 g.shortestPath("1", "5", path); // = { "1", "3", "6", "5" }

Deliverables

Please submit complete projects as zipped folders. The zipped folder should contain:

    • Graph.cpp (Your written Graph class)

    • Graph.hpp (Your written Graph class)

    • GraphBase.hpp (The provided base class)

    • PP5Test.cpp (Test file)

    • catch.hpp (Catch2 Header)

And any additional source and header files needed for your project.

Hints

Though it may be appealing to use an adjacency matrix, it might be simpler to complete this algorithm using an adjacency list for each vertex.

I suggest using a separate class for your edge and vertex.

Remember to write a destructor for your graphs!
Rubric

Any code that does not compile will receive a zero for this project.


Criteria
Points


Should calculate the distance of the shortest path for graph 1
5


Should have the labels for the shortest path for graph 1
5


Should calculate the distance of the shortest path for graph 2
5


Should have the labels for the shortest path for graph 2
5


Should calculate the distance of the shortest path for graph 3
5


Should have the labels for the shortest path for graph 3
5


Code implements Dijkstra's Algorithm
6


Code uses object oriented design principles
2
(Separate headers and sources, where applicable)





Code is well documented
2


Total Points
40