1
\$\begingroup\$

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();
}

\$\endgroup\$
2
\$\begingroup\$

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"; 
}
\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – PnotNP Aug 15 at 22:34
  • \$\begingroup\$ @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. \$\endgroup\$ – Martin York Aug 16 at 0:09
  • \$\begingroup\$ @PnotNP Tried to refactor your djikstras. Have not compiled it so it may need some work. \$\endgroup\$ – Martin York Aug 16 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.