2
\$\begingroup\$

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 & start, Node & finish);

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

   unsigned int* getPrev() const;
   void setPrev(unsigned int* prev);
   QVector<unsigned int> makePath(int target);

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

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

   class Compare
   {
   public:
      bool operator() (std::pair<Node*, int> a, std::pair<Node*, int> b)
      {
         return a.second > 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& start, Node& finish)
{
   QVector<Node> nodes=_gps.graph().nodes();

   std::priority_queue<std::pair<Node*,int>,std::vector<std::pair<Node*, int>>,Compare> q;

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

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

      if (*minNode == finish) {
         return;
      }
      int minNodeId = minNode->id();
      for (QMap<Node*, unsigned short>::iterator iterator=nextNodes.begin(); iterator != nextNodes.end(); iterator++) {
         Node* nextNode = iterator.key();
         int altDist = _dist[minNodeId] + nextNodes.value(nextNode);
         int nextNodeId = nextNode->id();
         if (altDist < _dist[nextNodeId]) {
            _dist[nextNodeId] = altDist;
            _prev[nextNodeId] = minNodeId;
            std::pair<Node*, int> 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<Node*, unsigned short> _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& other);
   void addNextNode(Node* node, unsigned short length);

   QMap<Node*, unsigned short> nextNodes() const;
};
\$\endgroup\$
  • \$\begingroup\$ Have you tried using std::vectorover QVector (and so on)? \$\endgroup\$ – JVApen Apr 15 '18 at 10:23
1
\$\begingroup\$
  1. Don't use QT objects when you are not working with QT constructs. There is no benefit to it.

  2. 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.

  3. Do not use a map. A std::vector is way faster/bettter for traversing than a std::map.

  4. You do a lot of copying data around:

    QMap<Node*, unsigned short> nextNodes = minNode->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.

\$\endgroup\$

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.