Dijkstra's Algorithm Programming Project 5

Dijkstra's Algorithm
COP 4530 Programming Project 5
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
(Separate headers and sources, where applicable) 2
Code is well documented 2
Total Points 40