﻿ Finding the shortest paths of a directed graph C++

# Finding the shortest paths of a directed graph C++

Over the last week, I have implemented a Digraph by parsing an input file. The graph is guaranteed to have no cycles. I have successfully created the graph, used methods to return the number of vertices and edges, and performed a topological sort of the graph. The graph is composed of different major courses and their prereqs. Here is my graph setup:

``````class vertex{
public:
typedef std::pair<int, vertex*> ve;
std::string course;
vertex(std::string c){
course = c;
}
};

class Digraph{
public:
typedef std::map<std::string, vertex *> vmap;
vmap work;
typedef std::unordered_set<vertex*> marksSet;
marksSet marks;
typedef std::deque<vertex*> stack;
stack topo;
void dfs(vertex* vcur);
void addEdge(std::string& from, std::string& to, int cost);
int getNumVertices();
int getNumEdges();
void getTopoSort();

};
``````

The implementation

``````//function to add vertex's to the graph
vmap::iterator iter = work.begin();
iter = work.find(course);
if(iter == work.end()){
vertex *v;
v = new vertex(course);
work[course] = v;
return;
}
}

//method to add edges to the graph
void Digraph::addEdge(std::string& from, std::string& to, int cost){
vertex *f = (work.find(from)->second);
vertex *t = (work.find(to)->second);
std::pair<int, vertex *> edge = std::make_pair(cost, t);
}

//method to return the number of vertices in the graph
int Digraph::getNumVertices(){
return work.size();
}

//method to return the number of edges in the graph
int Digraph::getNumEdges(){
int count = 0;
for (const auto & v : work) {
}
return count;
}

//recursive function used by the topological sort method
void Digraph::dfs(vertex* vcur) {
marks.insert(vcur);
if (marks.find(suc) == marks.end()) {
this->dfs(suc);
}
}
topo.push_front(vcur);
}

//method to calculate and print out a topological sort of the graph
void Digraph::getTopoSort(){
marks.clear();
topo.clear();
for (const auto & v : work) {
if (marks.find(v.second) == marks.end()) {
this->dfs(v.second);
}
}
// Display it
for (const auto v : topo) {
std::cout << v->course << "\n";
}
}
``````

For the last part of my implementation, I have been trying to do 2 things. Find the shortest path from the first vertex to every other vertices, and also find the shortest path that visits every vertex and returns to the first one. I am completely lost on this implementation. I assumed from reading I need to use Dijkstra's algorithm to implement this. I have been trying for the last 3 days to no avail. Did i set up my digraph in a bad way to implement these steps? Any guidance is appreciated.