Dijkstra implementation for large graphs I am implementing the Dijkstra algorithm for a large graph (40k nodes, 100k arcs). For shorter paths the searchtime is under a second for larger ones (from one end to the other) it takes quite some minutes to do it. I am also drawing the path after the search, so I am using some Qt objects. How could I make it faster? I feel like I am losing time when I search the neighbors because of the map structure.

This is the class:

class PathFinder {
public:
   void findPath2(const Node &amp; start, Node &amp; finish);

   static PathFinder&amp; getInstance();
   PathFinder();
   PathFinder(Gps gps);
   ~PathFinder();

   unsigned int* getPrev() const;
   void setPrev(unsigned int* prev);
   QVector&lt;unsigned int&gt; makePath(int target);

   GraphicNode* getTo();
   GraphicNode* getFrom();

   void setTo(GraphicNode* node);
   void setFrom(GraphicNode* node);

   class Compare
   {
   public:
      bool operator() (std::pair&lt;Node*, int&gt; a, std::pair&lt;Node*, int&gt; b)
      {
         return a.second &gt; b.second;
      }
   };


private:
   static PathFinder* _pathfinder;
   Gps _gps;
   GraphicNode* _from;
   GraphicNode* _to;

   unsigned int* _prev;
   unsigned int* _dist;
   unsigned int _notVisited;

   bool selectedNode = false;


   Node* getMinNode();
   bool hasNotVisited();
};


This is the search function:

void PathFinder::findPath2(const Node&amp; start, Node&amp; finish)
{
   QVector&lt;Node&gt; nodes=_gps.graph().nodes();

   std::priority_queue&lt;std::pair&lt;Node*,int&gt;,std::vector&lt;std::pair&lt;Node*, int&gt;&gt;,Compare&gt; q;

   _dist[start.id()] = 0;
   for (int i = 0; i &lt; nodes.size(); i++) {
      std::pair&lt;Node*, int&gt; p = std::make_pair(const_cast&lt;Node*&gt;(&amp;nodes.at(i)), _dist[i]);
      q.push(p);
   }

   while (!q.empty()) {
      std::pair&lt;Node*, int&gt; top = q.top();
      q.pop();
      Node* minNode = top.first;
      QMap&lt;Node*, unsigned short&gt; nextNodes = minNode-&gt;nextNodes();

      if (*minNode == finish) {
         return;
      }
      int minNodeId = minNode-&gt;id();
      for (QMap&lt;Node*, unsigned short&gt;::iterator iterator=nextNodes.begin(); iterator != nextNodes.end(); iterator++) {
         Node* nextNode = iterator.key();
         int altDist = _dist[minNodeId] + nextNodes.value(nextNode);
         int nextNodeId = nextNode-&gt;id();
         if (altDist &lt; _dist[nextNodeId]) {
            _dist[nextNodeId] = altDist;
            _prev[nextNodeId] = minNodeId;
            std::pair&lt;Node*, int&gt; p = std::make_pair(nextNode, _dist[nextNodeId]);
            q.push(p);
         }
      }
   }
}


This is the structure of the node, it contains a map to its neighbors with the weight as the value (x and y are coordinates for drawing it later on, don't mind those):

class Node {
private:
   unsigned short _id;
   double _y;
   double _x;
   QMap&lt;Node*, unsigned short&gt; _nextNodes;
   bool _visited = false;


public:
   Node();
   Node(unsigned short id, double longitude, double latitude);

   unsigned short id() const;
   double y() const;
   void setY(double y);
   double x() const;
   void setX(double x);

   bool operator==(const Node&amp; other);
   void addNextNode(Node* node, unsigned short length);

   QMap&lt;Node*, unsigned short&gt; nextNodes() const;
};
Don't use QT objects when you are not working with QT constructs. There is no benefit to it.
Your node::_id is unsigned shirt, which for MSVS has a range of 0 to 65,535. Be aware of that when you graph grows.
Do not use a map. A std::vector is way faster/bettter for traversing than a std::map. 
You do a lot of copying data around:

QMap&lt;Node*, unsigned short&gt; nextNodes = minNode-&gt;nextNodes();



That is a copy of all neighbors everytime you access a node during your search. If you really need the temporary, which you dont then at least make this a reference.