Dijkstra's implementation in c++ with STL priority_queue

Question

This is dijkstras shortest path algorithm implementation in c++ using priority_queue STL.

Looking for two things: a) Correctness of algorithm itself and b) Any improvement suggestions.

/* 3
 -----> b ----------->d
 10/ -1-- ^ | 1 ^/ |
 / / | | ------// 1|
 x v 2|11| / /-1-- |
 \ | v / v V
 \-----> c -----------> e
 1 8
*/
class EdgeNode
{
 public:
 char label;
 int weight;
 EdgeNode(char l = 0, int w = 0) : label(l), weight(w) {}
};
using EdgeNodes = vector<EdgeNode *>;
class Graph
{
 public:
 unordered_map<char, EdgeNodes *> adj;
 void addNode(char node)
 {
 if(adj.find(node) == adj.end()) {
 adj[node] = new EdgeNodes();
 }
 }
 void addEdge(char start, char end, int weight)
 {
 if(adj.find(start) != adj.end()) {
 for(auto node : *adj[start]) {
 if(node->label == end) {
 node->weight = weight;
 return;
 }
 }
 } else {
 adj[start] = new EdgeNodes();
 }
 if(end) {
 adj[start]->push_back(new EdgeNode(end, weight));
 }
 }
 void get_parent(unordered_map<char, char>& parent, char c)
 { 
 cout << "Parent chain of \'" << c << "\' =";
 while((parent.find(c) != parent.end()) && parent[c]) {
 cout << parent[c] << ", ";
 c = parent[c];
 }
 cout << endl;
 }
 void get_distance(unordered_map<char, int>& dist)
 {
 cout << "distances => ";
 for(auto a : dist) {
 cout << "(" << a.first << "=" << a.second << ") ";
 }
 cout << endl;
 }
 void djikstras()
 {
 unordered_set<char> visited;
 unordered_map<char, int> dist;
 unordered_map<char, char> parent;
 using Pair = pair<char, int>;
 priority_queue<Pair, vector<Pair>, greater<Pair>> pq; 
 char snode = 'x';
 visited.insert(snode);
 dist[snode] = 0;
 parent[snode] = 0;
 pq.push(make_pair(snode, 0));
 while(!pq.empty()) {
 Pair front = pq.top(); pq.pop();
 for(EdgeNode *edge : *adj[front.first]) {
 if(visited.find(edge->label) == visited.end()) {
 dist[edge->label] = dist[front.first] + edge->weight;
 visited.insert(edge->label);
 parent[edge->label] = front.first; 
 pq.push(make_pair(edge->label, dist[edge->label]));
 } else {
 /* //Parent comparison not needed in directed graph for djikstras
 //Its anyways useless because distance back to parent will always be larger
 if(parent[front.first] == edge->label) {
 cout << "Parent " << front.first << " = " << parent[front.first] << endl;
 continue;
 }*/
 if(dist[edge->label] > (dist[front.first] + edge->weight)) {
 dist[edge->label] = dist[front.first] + edge->weight;
 parent[edge->label] = front.first;
 pq.push(make_pair(edge->label, dist[edge->label]));
 } 
 } 
 } 
 } 
 get_distance(dist);
 get_parent(parent, 'e');
 }
};
int main(void)
{
 Graph g;
 g.addEdge('x', 'c', 1); g.addEdge('x', 'b', 10);
 g.addEdge('b', 'x', 1); g.addEdge('b', 'c', 11); g.addEdge('b', 'd', 3);
 g.addEdge('c', 'b', 2); g.addEdge('c', 'd', 1); g.addEdge('c', 'e', 8);
 g.addEdge('d', 'c', 1); g.addEdge('d', 'e', 1);
 g.addNode('e');
 g.djikstras();
}

• Loki Astari: stackoverflow.com/a/3448361/14065

Answer 1

Ohhh. Don't do this:

using EdgeNodes = vector<EdgeNode *>;
unordered_map<char, EdgeNodes *> adj;

Now you need to manage the memory of the EdgeNodes. Simply declare it as a value type:

using EdgeNodes = vector<EdgeNode>; // Remove the star
unordered_map<char, EdgeNodes> adj; // Remove the star.

To make the rest of your code simpler I would define a way to compare the EdgeNodes.

class EdgeNode
{
 public:
 char label;
 int weight;
 EdgeNode(char l = 0, int w = 0) : label(l), weight(w) {}
 // Compare a Node against a label
 bool operator==(char l) {return label == l;}
};

This makes your add functions simpler:

 void addNode(char node)
 {
 adj.insert({node, EdgeNodes{}});
 }
 void addEdge(char start, char end, int weight)
 {
 auto& dest = adj[node].second;
 // See if there is already a link to the destination.
 // This uses the `operator==` we defined above to compare
 // each node against `end`.
 auto find = std::find(std::begin(dest), std::end(dest), end);
 if (find != std::end(dest)) {
 // If we already have it update the weight. 
 find->weight = weight;
 }
 else {
 // otherwise add it to the end.
 dest.emplace_back(end, weight);
 }
 }

Don't be lazy:

 Pair front = pq.top(); pq.pop();

Split it over two lines. Its easy to write new code. Its hard to read other people's code. Don't make it difficult for them.

 Pair front = pq.top(); // Get the top item
 pq.pop(); // Pop it from the queue.

The dijkstras algorithm looks ok.

Things to look at:

• I find it a bit dense to read and it took me a while to understand it but nothing technically wrong with it.
• I might have used a single map for parent/distance calculations rather than two distinct structures.
• Checking inclusion in the visited list is usually done on the node as it is popped of the dq not when pushing it onto the list. This may be a bug.
• Normall you pass start and end as parameters to djikstras

Let me re-try a refactor:

void djikstras(char snode, char end)
{
 using ParentEdge = std::pair<char, EdgeNode>;
 auto comp = [](ParentEdge const& l, ParentEdge const& r){return l.second.weight < r.second.weight;};
 unordered_map<char, EdgeNode> retrace; 
 priority_queue<ParentEdge, vector<ParentEdge>, comp> pq; 
 // special case the snode is its own parent.
 retrace[snode] = EdgeNode(snode, 0);
 pq.push(ParentEdge(snode, EdgeNode(snode, 0)));
 while(!pq.empty()) {
 // Get details of next node.
 ParentEdge front = pq.top();
 char& parent = front.first;
 char& current = front.second.label;
 int& weight = front.second.weight;
 pq.pop();
 if (current === end) {
 // Did we find the destination.
 printRoute(retrace, end);
 return;
 }
 if (retrace.find(current) != retrace.end()) {
 // Already found cheapest route to here.
 continue;
 }
 // Found cheapest route to this point. Add info to the structures.
 retrace[current] = EdgeNode(parent, retrace[parent].weight + weight);
 // Add children to the frontier list
 for(EdgeNode edge : adj[current]) {
 pq.push(ParentEdge(current, edge));
 }
 } 
 std::cout << "Failed to find route from start to finish\n"; 
}

• PnotNP: Forgot why I did pointer thingy, but agree with you. About the splitting on two lines, I with we had pq.pop_and_assign() function. Any comments on dijkstra's algo itself?
• Loki Astari: @PnotNP The algorithm I find to hard to read (way to dense). I provided a comment on the answer to a simpler implementation I wrote.
• Loki Astari: @PnotNP Tried to refactor your djikstras. Have not compiled it so it may need some work.