# Dijkstra's algorithm using a specific structure

I have implemented Dijkstra's algorithm using a slightly modified version of the structure and class posted here. Unfortunately, I have ruined the efficiency. I am intent on using this structure. I will NOT use BOOST. Any STL algorithms are acceptable.

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <list>
#include <set>
#include <algorithm>
struct vertex {
typedef std::pair<double, vertex*> vert;                                      // weight, destination pair
std::vector<vert> adj;                                                        // vector holding <weight of edge, destination vertex>
std::string name;                                                             // to hold name/title of vertex
vertex(std::string str) : name(str) {}                                        // struct constructor pass name to vertex.name
};

class graph {

typedef std::map<std::string, vertex *> vertmap;                              // name, vertex pair
vertmap port;                                                                 // map holding <name of vertex, pointer to vertex>
std::vector<std::string> travel;                                              // vector holds BFS, DFS, or shortest distance
typedef std::pair<std::string, bool> visited;                                 // visited name, bool pair
void depthFirstUtil(const std::string&);                                      // helper for depth first search
public:
graph() { }
graph(std::vector<vertex*> edges);
void addedge(const std::string&, const std::string&, const double);           // add a weighted edge to the graph
std::vector<std::string> getDepthFirst(const std::string&);
std::vector<std::string> getBredthFirst(const std::string&);
typedef std::pair<double, std::string> dPair;
std::vector<dPair> getShortestDistance(const std::string&);
};

int main() {
graph mygraph;
std::string myverts[6] = { "v0", "v1", "v2", "v3", "v4", "v5" };

std::cout << "Depth first: ";
for (auto ver : mygraph.getDepthFirst(myverts[0])) std::cout << ver << " ";
std::cout << std::endl << std::endl << "Bredth first: ";
for (auto ver : mygraph.getBredthFirst(myverts[0])) std::cout << ver << " ";
std::cout << std::endl << std::endl << "Shortest distance: " << std::endl;
for (auto ver : mygraph.getShortestDistance(myverts[0])) std::cout << ver.second << " " << ver.first << std::endl;
system("pause");
return 0;
}

graph::graph(std::vector<vertex*> edges) {
for (auto edge : edges) for (auto dest : edge->adj) addedge(edge->name, dest.second->name, dest.first);
}

void graph::depthFirstUtil(const std::string& inName) {
travel.push_back(inName);                                                                   // mark inName as visited
std::vector<vertex::vert> avec = port.at(inName)->adj;                                      // Recur for all the vertices adjacent to this vertex
for (auto i : avec)
if (std::find(travel.begin(), travel.end(), i.second->name) == travel.end())
depthFirstUtil(i.second->name);
}

std::vector<std::string> graph::getDepthFirst(const std::string& begin) {
travel.clear();                                                                             // Mark all the vertices as not visited
depthFirstUtil(begin);                                                                      // Call the recursive helper function to print DFS traversal
return travel;
}

std::vector<std::string> graph::getBredthFirst(const std::string& name) {
travel.clear();
std::list<std::string> queue;                                                               // Create a queue for BFS
queue.push_back(name);
while (!queue.empty()) {
travel.push_back(queue.front());                                                        // Dequeue a vertex from queue and store it
queue.pop_front();
for (auto i : port.at(travel.back())->adj)                                              // Get all adjacent vertices of the dequeued vertex
if((std::find(travel.begin(), travel.end(), i.second->name) == travel.end())        // If an adjacent vertex has not been visited, then enqueue it
&& (std::find(queue.begin(), queue.end(), i.second->name) == queue.end()))      // IF NOT IN TRAVEL AND NOT IN QUEUE!
queue.push_back(i.second->name);
}
return travel;
}

vertmap::iterator itr = port.find(name);
if (itr == port.end()) {
vertex *v = new vertex(name);
port[name] = v;
return v;
}
else return itr->second;
}

void graph::addedge(const std::string& from, const std::string& to, const double weight) {
std::pair<double, vertex *> edge = std::make_pair(weight, t);
}

typedef std::pair<double, std::string> dPair;
std::vector<dPair> graph::getShortestDistance(const std::string& start) {
travel.clear();
std::vector<dPair> nameDist;
std::vector<dPair> nameDistCopy;
std::string vertName;
std::set<vertex*> queue;
double totDist;
for (auto i : port) {
dPair portPair = std::make_pair(INFINITY, i.first);
nameDist.push_back(portPair);
nameDistCopy.push_back(portPair);
queue.insert(i.second);
}
auto srcItr = std::find_if(nameDist.begin(), nameDist.end(), [=](const dPair vName) {
return vName.second == start;
});
double minDist = (*srcItr).first = 0;
while (!queue.empty()) {
auto vNameItr = std::min_element(nameDistCopy.begin(), nameDistCopy.end());
vertName = (*vNameItr).second;
minDist = (*std::find_if(nameDist.begin(), nameDist.end(), [=](const dPair element) {
return element.second == vertName;
})).first;
auto qVertItr = std::find_if(queue.begin(), queue.end(), [=](const vertex* element) {
return element->name == vertName;
});
vertex *minVert;
minVert = *qVertItr;
queue.erase(minVert);
for (auto neighbor : minVert->adj) {
totDist = minDist + neighbor.first;
auto distItr = std::find_if(nameDist.begin(), nameDist.end(), [=](const dPair vName) {
return vName.second == neighbor.second->name;
});
if (totDist < (*distItr).first) {
(*distItr).first = totDist;
}
}
auto erItr = std::find_if(nameDistCopy.begin(), nameDistCopy.end(), [=](const dPair vName) {
return vName.second == minVert->name;
});
nameDistCopy.erase(erItr);
}
return nameDist;
}


I would very much appreciate any/all optimization of the getShortestDistance function. I am fine with the implementation of the other functions.

• I am intent on using this structure Which part of program or data structure(s) does this refer to? (I conclude it does not to getShortestDistance ().) – greybeard Dec 11 '16 at 12:28
• It refers to the structure defined in the class. struct vertex {...}; – phabi0 Dec 16 '16 at 19:08

Yes, your implementation of Dijkstra's shortest path algorithm is far from efficient. Here is a pseudo code for a better one:

DijkstraSearch(graph g, int source, int target):
OPEN = std::priority_queue<int>
CLOSED = std::unordered_set<int>
parent_map = std::unordered_map<int, int>
distance_map = std::unordered_map<int, double>

OPEN.push(source)
parent_map[source] = source
distance_map[source] = 0.0

while (OPEN not empty):
current = OPEN.extractMinimum()
if current is target:
return traceback_path(source, target, parent_map)
if CLOSED contains current:
continue

for neighbor in graph.neighbors_of(current):
if CLOSED contains neighbor:
continue
double tentative_distance = distance_map[current] + graph.weight(current, neighbor)
if neighbor not in parent_map.keys() or tentative_distance < distance_map[neighbor]:
distance_map[neighbor] = tentative_score
parent_map[neighbor] = current
OPEN.insert(neighbor, tentative_distanse) # insert(node, priority)
error "No path"

traceback_path(source, target, parent_map):
path = []
current = target
while (true):
path.append(current)
current = parent_map[current]
if current == source:
break
path.reverse()
return path


If implemented correctly, the above will run in $\mathcal{O}((m + n) \log n)$. If you, however, use a Fibonacci heap, the running time will improve to $\mathcal{O}(m + n \log n)$.

Actually, the algorithm posted by op (me) fails to function properly. If you were to input "v5" as the starting point, the only results would be the distances from "v5" to "v5" == 0, and "v5" to "v4" == 3. The intent of the algorithm (in this case) is to return the shortest distance from some arbitrary starting vertex to each vertex in the graph. To remedy this only (does NOT improve efficiency), the starting vertex should be set to 0 in both the nameDist pair and the nameDistCopy pair. Further, when the total distance is less than the currently stored nameDist pair it should be updated in both nameDist and nameDistCopy.