Dijkstra's algorithm using a specific structure

Question

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
 vertex* addvertex(const std::string&); // add a vertex to the graph
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" };
 mygraph.addedge(myverts[0], myverts[1], 2);
 mygraph.addedge(myverts[0], myverts[5], 9);
 mygraph.addedge(myverts[1], myverts[2], 8);
 mygraph.addedge(myverts[1], myverts[3], 15);
 mygraph.addedge(myverts[1], myverts[5], 6);
 mygraph.addedge(myverts[2], myverts[3], 1);
 mygraph.addedge(myverts[4], myverts[2], 7);
 mygraph.addedge(myverts[4], myverts[3], 3);
 mygraph.addedge(myverts[5], myverts[4], 3);
 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;
}
vertex* graph::addvertex(const std::string &name) {
 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) {
 vertex *f = (addvertex(from));
 vertex *t = (addvertex(to));
 std::pair<double, vertex *> edge = std::make_pair(weight, t);
 f->adj.push_back(edge);
}
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.

• greybeard: 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 ().)
• phabi0: It refers to the structure defined in the class. struct vertex {...};

Answer 1

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
 CLOSED.add(current)
 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)\$.

Answer 2

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.