Dijkstra's implementation in c++ with STL priority_queue
Ohhh. Don't do this:

using EdgeNodes = vector&lt;EdgeNode *&gt;;
unordered_map&lt;char, EdgeNodes *&gt; adj;


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

using EdgeNodes = vector&lt;EdgeNode&gt;;      // Remove the star
unordered_map&lt;char, EdgeNodes&gt;      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&amp; 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-&gt;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&lt;char, EdgeNode&gt;;
    auto  comp = [](ParentEdge const&amp; l, ParentEdge const&amp; r){return l.second.weight &lt; r.second.weight;};

    unordered_map&lt;char, EdgeNode&gt;                        retrace;    
    priority_queue&lt;ParentEdge, vector&lt;ParentEdge&gt;, comp&gt; 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&amp;      parent  = front.first;
        char&amp;      current = front.second.label;
        int&amp;       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 &lt;&lt; "Failed to find route from start to finish\n"; 
}